algorithm - BinarySearch 坐标之间的距离

Question

我应该如何使用二进制搜索来查找排序数组中相邻数字之间的距离是否大于 N？例如:

Input: 2 5 8 11 16  
Distance: 4

所以我们应该得到邻居之间有这样的距离的答案。 (11 到 16 岁之间)

编辑:让我更清楚为什么我想用二进制搜索来做到这一点。
假设 INPUT 数组未排序。例如:

Input: 11 8 2 16 5

然后你应该对数组进行排序，看看哪些是邻居。那么在我们有一个排序列表之后，这不是通过二分搜索的一些变异来找到距离的最佳方法吗？

Answer 1

在最坏的情况下，当所有数字在 N 处等间距时，您不能使用二分查找。

二分搜索和其他分而治之算法的思想是，您在每一步消除大约一半的剩余范围。当所有项目都以 N 间隔时，三个或更多连续项目的每个范围都可能包含一对距离为 > N 的邻居，因此您不能消除任何一个正在考虑的两个子范围。您最终将检查每一对连续的项目，花费您 O(NumItems)。

也就是说，由于潜在的剪枝机会，您可能可以优化一般情况以比 O(NumItems) 做得更好。