Algorithm for approximate search in sorted integer list

Question

Hi All,

Consider an array of integers (assumed to be sorted); I would like to find the array index of the integer that is closest to a given integer in the fastest possible way. And the case where there are multiple possibilities, the algorithm should identify all.

Example: consider T=(3, 5, 24, 65, 67, 87, 129, 147, 166), and if the given integer is 144, then the code should identify 147 as the closest integer, and give the array index 7 corresponding to that entry. For the case of 66, the algorithm should identify 65 and 67.

Are there O(1) or at least O(log N) algorithms to do this? The direct search algorithm (binary-search, tree-search, hashing etc.) implementation won't work since those would require perfect matching. Is there any way these can be modified to handle approximate search?

I am developing a C code.

Thanks

Answer 1

Do binary search until you get down to a single element. If there is a match, walk along your neighbors to find other matches. If there is no match, look at your immediate neighbors to find the closest match.

Answer 2

Properly implemented binary-search should do the trick -- as long as you identify the moment where your search range decreased to two items only. Then you just pick the closest one. Complexity: O(log n).