我知道二进制搜索具有 O(logn) 的时间复杂度来搜索排序数组中的元素 . 但是，让我们说如果不选择中间元素，我们选择一个随机元素，它将如何影响时间复杂度 . 它仍然是 O(logn) 还是其他的东西？
O(logn)
例如：一个大小为18的数组中的传统二进制搜索将会像18 - > 9 - > 4那样下降...
我修改的二进制搜索ping一个随机元素，并决定根据值删除右边部分或左边部分 .
让我们假设我们有一棵大小为18的树 . 我正在寻找的数字是第一点 . 在最坏的情况下，我总是随机选择最高的数字，（18-> 17-> 16 ......） . 有效地仅在每次迭代中消除一个元素 . 所以它变成了线性搜索：O（n）时间
我的尝试：
让 C(N) 是 N 元素中搜索所需的平均比较次数 . 为简单起见，我们假设算法仅在剩下单个元素时终止（在与键严格相等时不提前终止） .
C(N)
N
由于枢轴值是随机选择的，剩余尺寸的概率是均匀的，我们可以写出重现
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)
这种复发的解决方案是Harmonic系列，因此行为确实是对数的 .
C(N) ~ Ln(N-1) + Gamma
请注意，这是自然对数，它比基数2对数好1.44倍！
我敢打赌，添加提前终止测试将进一步改善日志基础（并保持日志行为），但同时将比较数量增加一倍，因此在全局范围内，在比较方面会更糟 .
2 回答
让我们假设我们有一棵大小为18的树 . 我正在寻找的数字是第一点 . 在最坏的情况下，我总是随机选择最高的数字，（18-> 17-> 16 ......） . 有效地仅在每次迭代中消除一个元素 . 所以它变成了线性搜索：O（n）时间
我的尝试：
让
C(N)是N元素中搜索所需的平均比较次数 . 为简单起见，我们假设算法仅在剩下单个元素时终止（在与键严格相等时不提前终止） .由于枢轴值是随机选择的，剩余尺寸的概率是均匀的，我们可以写出重现
然后
和
这种复发的解决方案是Harmonic系列，因此行为确实是对数的 .
请注意，这是自然对数，它比基数2对数好1.44倍！
我敢打赌，添加提前终止测试将进一步改善日志基础（并保持日志行为），但同时将比较数量增加一倍，因此在全局范围内，在比较方面会更糟 .