编程珍珠问题:在二进制搜索中检查排序数组

Question

在Programming Pearls(第二版)第5列,问题5中,问题是关于在未排序的数组上实现二进制搜索.

如何以低于O(n-1)的成本为功能添加部分检查？

我知道您可以检查每次迭代并获得O(log n),但后面的提示表明存在O(1)解决方案.

那是什么解决方案？

Answer 1

概括

正如OP所说，部分检查数组是否已排序以便二分搜索适用可以在O(log n)和O(1)中完成。O(log n) 方法是对照前一个探针检查每个探针，以确保其比较正确（小于、大于）。O(1) 方法只是检查二分查找找到的最后一个元素及其旁边的一个元素，这样如果没有找到所需的元素，至少可以找到正确的插入位置。如果找到了所需的元素，那么这是一个很好的 O(1) 部分检查。

更长的解释

代码块之前的问题部分表明，一个常见问题是在未排序的数组上使用二分搜索。基本上，如何使用部分检查来检查数组是否以小于 O(n-1) 成本排序？

O(log n) 解决方案是检查每个二分搜索探针相对于前一个探针的网格（小于或大于预期）。这并不能保证数组已排序，但它是一个很好的部分检查。

我能想到的唯一 O(1) 检查是检查搜索的最终位置，使其值和相邻值与搜索元素应该在哪里的想法相吻合，即使未找到该元素。这是一个非常好的部分检查：如果找到该元素，那么事情可能工作正常。如果不是，则检查它应该在的位置周围的元素，以便有一个比搜索到的元素小一个，然后一个比搜索到的元素大。然而，我确实意识到，以这种方式检查意味着二分搜索（即 O(log n)）已经完成，所以我不知道这是否真的是 O(1)。然而，它只在整体搜索中增加了 O(1)，所以我认为它是适用的。