BinarySearch for distance between coordinates

Question

How to use binary search to find if there is a distance between adjacent numbers greater than N in a sorted array? For instance:

Input: 2 5 8 11 16 Distance: 4 

So, we must get an answer that there is such a distance between neighbors. (between 11 and 16)

EDIT: let me clarify why I want to do this using binary search.
Suppose the INPUT array is not sorted. Example:

 Input: 11 8 2 16 5 

Then you have to sort the array to see which of them are neighbors. So, after we have a sorted list, is not the best way to find the distance with some mutation of binary search?

Answer 1

You cannot use binary search in the worst case, when all numbers are evenly spaced on N

The idea of ​​binary search and other separation and rest algorithms is that you delete about half of the remaining range at each step. When all elements are located at a distance of N , each range of three or more consecutive elements may potentially contain a pair of neighbors with a distance > N , so you cannot eliminate one of the two sub-ranges under consideration. You will eventually learn each pair of consecutive elements, the cost of which will be O(NumItems) .

However, you can probably optimize the general case to do significantly better than O(NumItems) due to possible cropping capabilities.

Answer 2

You (well, I) did not want to: binary search requires a sorted list, and you will spend more time sorting this list (from pairs of neighboring elements ordered by their distance) than just scanning the list.