Algorithm for approximate search in sorted integer list

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) algori开发者_Go百科thms 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

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.

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).

I know this is really old - but for other people looking for an answer: If implementing a regular binary search algorithm with a target value, will of course return -1 if the target value was not found. BUT - in this case, the value of Low/Left will be in the index which the target number was supposed to be positioned in the sorted list. So in this example, the value of Low at the end of the search will be 7. Which means if 144 was actually inside the array, 147 will be to it's right, and 129 will be to it's left. All there's left to do is to check which difference is smaller between the target to 147 and 129, and return it.