问题是“建议一个采用排序数组和 X 的算法,如果在数组中找不到它,它将返回数组中 X 的索引 return -1 ,算法的时间复杂度应该是 O( log d ) 而d是小于X的元素个数
除了查看中间索引并比较它是否小于或大于 X 之外,我想不出其他事情,然后递归地做同样的事情。但我不认为它是 O(log d ) 。我有作业要交,但我不知道该做什么。
最佳答案
Exponential search是 O(log d)。
从 upper = 0
开始,将值 array[upper]
与 value
进行比较。如果小于 value
,更新 upper = (upper + 1) * 2;
直到 array[upper] >= value
。如果相等,则返回upper
,否则执行binary search在 [upper/2, upper)
之间。
在 JavaScript 中它看起来像这样:
function exponentialSearch (array, value) {
let upper = 0;
// exponential gallop
while (array[upper] < value) upper = (upper + 1) * 2;
if (array[upper] === value) return upper;
// binary search
for (let lower = upper / 2; upper > lower; ) {
const bisect = lower + Math.floor((upper - lower) / 2);
if (array[bisect] > value) upper = bisect;
else if (array[bisect] < value) lower = bisect;
else return bisect;
}
return -1;
}
关于arrays - 给我 O(logd) 的算法是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55307297/