二分查找算法

二分查找法是一个在已经有序的数组里边查找具体某个值的算法。

算法原理

在查找过程中，需要先找到数组中间位置的值，如果相等，就找到了相对应的元素，并返回它的索引。如果中间值小于要查找的值，就会把左半部分省去，再从右侧开始搜索，同样的找到右侧部分的中间元素，再判断是否相等。 如果大于的话，就去查找左半部分，利用同样的算法，直到找到对应的值。 需要注意的是，要查找的数组必须是已经排好序的，否则无法判断该舍去哪半部分元素。

JavaScript 实现

好，我们接下来看一下二分查找在 javascript 中的实现方式。 首先定义二分查找函数，接收要查找的数组作为第一个参数，然后要查找的值作为第二个参数：

function binarySearch(arr, value) {}

之后我们在函数中定义 start 保存起始索引，定义 end 保存结束索引，根据这两个值我们来计算中间索引，获取数组中间的值：

function binarySearch(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);
}

这个 middle 我们直接使用 Math.floor((start + end) / 2)，这样当数组元素有偶数个时，数组可能有两个中间值，我们把靠左的那一个作为中间值。 接下来使用 while 循环反复查找中间值，判断条件是：如果数组的中间值不等于要查找的值，并且 start <= end，就一直查找。也就是说，循环会在找到对应的值后停止，或者这个值不存在，也会停止循环：

function binarySearch(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while (arr[middle] !== value && start <= end) {}
}

之后在循环里面判断，如果要查找的值小于数组的中间值，就去搜索左半部分。 end 就等于 middle - 1。这样就把结束索引定位在了左半边，如果大于的话，就把 start 设为 middle + 1，这样就把要查找的数组定义到了右半边，最后重新计算 middle 的值，找到剩下的这一半数组的中间值：

function binarySearch(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
}

在循环结束之后，我们需要判断是不是找到了这个值，因为还有可能是没找到这个值而退出了循环。判断 arr[middle] 的值是不是等于要查找的值，如果是，就返回 middle ，也就是这个值的索引。那么如果不是，就返回 -1，表示没有找到：

function binarySearch(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  return arr[middle] === value ? middle : -1;
}

我们来测试一下，定义一个数组，包含 9 个元素，然后我们来查找 7。运行一下可以看到它找到了 7 这个元素，索引是 6。如果我们修改一下，查找一个不存在的值，例如 10 ，那么它就返回 -1：

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(arr, 7)); // 6
console.log(binarySearch(arr, 10)); // -1