时间戳

首页 > 解决方案 > 提高我的二进制搜索算法的速度

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

问题描述

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

标签： javascriptalgorithmbinary-search

解决方案

您将值作为索引。如果您采用比索引更大的值，您会看到您的代码不起作用。

相反，您可以获取middleforleft或rightif not found 的索引。

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

推荐阅读