二分查找坐标之间的距离

Question

如何使用二分查找在已排序的数组中查找相邻数字之间的距离是否大于N？例如：

Input: 2 5 8 11 16  
Distance: 4

因此，我们应该得到这两个相邻元素之间的距离（在11和16之间）的答案。

编辑：让我更清楚地解释为什么我想用二分查找来做这件事。
假设输入数组是未排序的。例如：

Input: 11 8 2 16 5

然后您应该对数组进行排序，以查看哪些是相邻的。所以在我们有了一个排序列表之后，使用二分搜索的某种变异方式来查找距离不是最好的方法吗？

- nyxz

Answer 1

你（或者说我）不应该使用二分查找：因为它需要一个有序列表，而你会花费更多的时间去排序这个列表（由相邻项对组成，按照它们之间的距离排序），比直接扫描列表要耗费更多的时间。

- Scott Hunter

---

为什么你必须这样做？难道不能基于修改后的二分查找采用其他方法吗？ - templatetypedef

二分查找需要一个有序列表，而你没有。再次强调，排序列表需要更多的工作量，比仅仅扫描它要多。 - Scott Hunter

但是你假设这是二分查找唯一可用的方法。我相当有信心你是正确的，而且在这里你无法使用二分查找，但我没有看到为什么不能使用类似于二分查找的算法来缩小数组。 - templatetypedef

好的，假设您得到了未排序的数组。那么您应该对其进行排序，以了解数组中相邻坐标之间是否存在大于N的距离。 - nyxz

这要看情况 -- 如果你只需要搜索一次列表，那么 Scott 是正确的：你可以在生成数据时直接搜索列表。但是，如果你需要多次搜索同一个列表，那么对距离进行排序以支持二分查找可能是值得的。 - Jerry Coffin

Answer 2

在最坏情况下，当所有数字等间隔排列为N时，您无法使用二进制搜索。

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

话虽如此，由于存在潜在的修剪机会，您可能可以优化一般情况，使其比O（NumItems）好得多。

- Sergey Kalinichenko