algorithm - 使用随机元素进行二分查找

Question

我知道二分搜索的时间复杂度为 O(logn) 来搜索排序数组中的元素。但是假设如果我们不选择中间元素，而是选择一个随机元素，它将如何影响时间复杂度。它仍然是 O(logn) 还是其他什么？

例如: 在大小为 18 的数组中进行传统的二进制搜索，将像 18 -> 9 -> 4 ...

我修改后的二分查找ping一个随机元素，并根据值决定删除右边的部分或左边的部分。

Answer 1

我的尝试:

设 C(N) 为在 N 元素中搜索所需的平均比较次数。为简单起见，我们假设算法仅在只剩下一个元素时终止(与 key 严格相等时不会提前终止)。

由于枢轴值是随机选择的，剩余大小的概率是统一的，我们可以写出递归

C(N) = 1 + 1/N.Sum(1<=i<=N:C(i))

然后

N.C(N) - (N-1).C(N-1) = 1 + C(N)

和

C(N) - C(N-1) = 1 / (N-1)

这个递归的解是调和级数，因此行为确实是对数的。

C(N) ~ Ln(N-1) + Gamma

请注意，这是自然对数，比以 2 为底的对数好 1.44 倍!

我敢打赌，添加提前终止测试会进一步改善对数基础(并保持对数行为)，但同时会增加一倍的比较次数，因此在全局范围内，它在比较方面会更糟。