Der*_*tle 2 arrays algorithm performance big-o
给定一个排序A[1...n]的键数组,以及x存储在其中的另一个键,A显示如何查找索引k,以便A[k] = x及时O(log(k)).
A[1...n]
x
A
k
A[k] = x
O(log(k))
我知道在排序数组上的二进制搜索O(logn)平均会完成,但O(logk)如上所述,对于排序数组,显示运行时间的最佳方法是什么？ 我感谢任何帮助.
O(logn)
O(logk)
War*_*Dew 5
进行指数搜索,从索引m = 1开始,然后每次加倍m,直到m处的数组元素大于x.然后,对最终m下面的数组子集进行常规二进制搜索.
归档时间：
11 年，10 月 前
查看次数：
141 次
最近记录：