提高我的二进制搜索算法的速度

Question

我在JavaScript写了一个二分查找算法：

function binarysearch(number, array) {
  let left = 0;
  let right = array.length - 1;
  let middle;

  while (right != left) {

    middle = Math.floor(left + (right - left) / 2);
    if (array[middle] == number) {
      return middle;
    }
    if (array[middle] < number) {
      left = array[middle];
      if (array[middle + 1] == number) {
        return middle + 1;
      }
    }
    if (array[middle] > number) {
      right = array[middle];
      if (array[middle - 1] == number) {
        return middle - 1;
      }
    }
  }
  return -1;
}

我想问一下我是否可以改进这个算法来更快地搜索或者这里是否有错误？

编辑：

谢谢大家的帮助，这个解决方案现在应该可以正常工作了：

function binarysearch(number, array) {
      let left = 0;
      let right = array.length - 1;
      let middle;
      while (left <= right) {
        middle = Math.floor(left + (right - left) / 2);
        if (array[middle] == number) {
          return middle;
        }
        if (array[middle] < number) {
          left = middle + 1;
        }
        if (array[middle] > number) {
          right = middle - 1;
        }
      }
      return -1;
    }

Answer 1

让它更简单

  let left = 0;
  let right = array.length - 1;
  let middle;

  while (right != left) {

    middle = Math.floor(left + (right - left) / 2);
    if (array[middle] == number) {
      return middle;
    }
    if (array[middle] < number) {
      left = array[middle] + 1;
    }
    if (array[middle] > number) {
      right = array[middle];
    }
  }
  return -1;
}

Answer 2

您正在以值作为指标。如果您采用比索引更大的值，您会发现您的代码不起作用。

相反，您可以使用 middle 的索引作为 left 或 right 如果找不到。

function binarysearch(number, array) {
    let left = 0,
        right = array.length - 1,
        middle;

    while (left <= right) {
        middle = Math.floor((left + right) / 2);
        if (array[middle] === number) return middle;
        if (array[middle] > number) right = middle - 1;
        else left = middle + 1;
    }
    return -1;
}

console.log(binarysearch(0, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(43, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(44, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(45, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(46, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(47, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(48, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(49, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(50, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(100, [43, 44, 45, 46, 47, 48, 49, 50]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

提高我的二进制搜索算法的速度

Improve speed of my binary search algorithm

javascript

algorithm

binary-search