binary search for closest index/ index's to a value with O(log n)

Question

I have sorted array (duplicates can exist) of objects with dateTime in milliseconds as a member to the objects, I want to get the index/index's of the array which has the least dateTime difference from currentTime. I thought of using binary search but it needs the key to be present in the array. I can use simple for loop but it will be O(n) is there a efficient binary search variant to get index/index's with O(log n) efficiency?.

What do you mean __'it needs the key to be present in the array'__ ? — fuyushimoya, Aug 03 '15 at 15:22
With a slightly modified binary search, you can keep track of the two narrowing endpoints of the array that surround your query datetime, find the two datetimes that are the immediate neighbors of your query datetime. Then one of those has to be the answer. — user2566092, Aug 03 '15 at 15:22
Have a look at [this answer](http://stackoverflow.com/a/21703870/1048572). The value doesn't need to be in the array to find the closest positions via binary search. — Bergi, Aug 03 '15 at 15:47
fuyushimoya: I thought binary search is for the search key to be existing in the sorted array/collection. — Prashanth, Aug 03 '15 at 16:43

IVlad · Answer 1 · 2015-08-03T15:42:29.503

I want to get the index/index's of the array which has the least dateTime difference from currentTime

So you want to find the largest value less than or equal to currentTime and the smallest value higher than or equal to currentTime. Your answer has to be one of these.

For the first one, you can write your binary search like this:

while left < right:
  m = left + (right - left) / 2
  if array[m] <= target: # using <= here to save the right index 
                         # in store in case the key exists
    left = m + 1
    store = m
  else:
    right = m

After this runs, store will contain the last index lower than or equal to target. Then you can check:

if array[store] == target:
  you found the target exactly
else:
  check array[store] and array[store + 1] (if not out of bounds) and pick the best.

binary search for closest index/ index's to a value with O(log n)

1 Answers1