arrays - 给我 O(logd) 的算法是什么

Question

问题是“建议一个采用排序数组和 X 的算法，如果在数组中找不到它，它将返回数组中 X 的索引 return -1 ，算法的时间复杂度应该是 O( log d ) 而d是小于X的元素个数

除了查看中间索引并比较它是否小于或大于 X 之外，我想不出其他事情，然后递归地做同样的事情。但我不认为它是 O(log d ) 。我有作业要交，但我不知道该做什么。

Answer 1

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;
}