CODEWITHSUNDEEP
search
Алекс Всилев
Алекс Всилев

Reputation: 3

Fast finding of nearest bigger element to a given parameter I in OrderedList

Lets say we have a OrderedList with int years in it.I have to find the years between year i and year n, but im having trouble finding the nearest element bigger than year i.I need something faster than linear algorithm complexity (O(n)).

Upvotes: 0

Views: 18

Answers (1)

Dakkaron
Dakkaron

Reputation: 6276

(Guessing you mean sorted list by ordered list, since ordered list wouldn't make much sense here. Otherwise sort that list before searching.)

Try binary search. What you do is the following:

  • Say you have a list of length n and are looking for the value k
  • Take the element a position n/2
  • If the element is smaller than k, take the right half of the list, starting at n/2 and ending at n
  • If the element is larger than k, take the left half of the list, starting at 0 and ending at n/2
  • If the element is equal k, end here.
  • repeat the search until your upper and lower limits of the search are only one field apart, or you have an element equal to k. In that case put that element as your lower limit and the next element after that as the higher limit. The higher limit is the value you are looking for. The lower limit should be the highest number lower or equal to k.

Upvotes: 1

Related Questions