如何使用二分搜索來查找排序數組中是否有大於N的鄰居數之間的距離？例如：BinarySearch座標之間的距離
Input: 2 5 8 11 16
Distance: 4
所以我們應該得到答案，即鄰居之間有這樣的距離。 （11與16）
編輯：讓我更清楚，爲什麼我要與二進制搜索做到這一點。
假設INPUT數組未經排序。例如：
Input: 11 8 2 16 5
然後你應該對數組進行排序，看看哪些是鄰居。所以在我們有了一個排序列表之後，這不是找到二進制搜索的一些變異的距離的最佳方法嗎？
不能使用在最壞的情況下，當所有的數字都在N等間隔的二進制搜索。
二進制搜索和其他分而治之算法的想法是，你消除大約一半的剩餘里程的每一步。當所有項目的間距爲N時，三個或更多個連續項目的每個範圍都可能包含一對距離爲> N的鄰居，因此您無法消除所考慮的兩個子範圍中的任何一個。你最終會檢查每一對連續的物品，花費你O(NumItems)。
這就是說，你也許可以優化一般情況下做的相當好，因爲潛在的修剪機會比O(NumItems)。
你（好，我）不會：二進制搜索需要一個排序列表，你會花更多的時間對該列表進行排序（對周邊的項目，通過他們的距離排序的），比你只需掃描清單。
你爲什麼要這樣做？有沒有其他方法基於修改的二進制搜索？ – templatetypedef 2012-01-11 21:44:43
二進制搜索需要一個排序列表，你沒有。而且，再次，對列表進行排序需要更多的工作，而不僅僅是掃描它。 – 2012-01-11 21:59:25
但是你認爲這是二進制搜索可以在這裏使用的唯一方法。我相當確信你是對的，並且你不能在這裏使用二分搜索，但是我沒有看到爲什麼不能使用削減數組的二進制搜索類算法的任何原因。 – templatetypedef 2012-01-11 22:00:48
很好的解釋。 – 2012-01-12 00:02:59