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

Question

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

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

标签： arraysalgorithmsortingtime-complexity

Answer 1

指数搜索是O(log d)。

从 开始upper = 0，将值array[upper]与进行比较value。如果小于value，则更新upper = (upper + 1) * 2;直到array[upper] >= value。如果相等，则返回upper，否则在之间进行二分查找[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;
}