算法之二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。二分查找法要求所查找列表必须为序列表。

算法步骤#

从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束。否则进行下一步。
如果指定要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
重复以上过程，直到找到目标元素的索引，查找成功。或者直到子数组为空，查找失败。

代码演示#

采用递归方式

function binarySearch(arr, target, start, end) {
  start = start || 0;
  end = end || arr.length - 1;
  let mid = Math.floor((start + end) / 2);
  if (target === arr[mid]) {
    return mid;
  } else if (target > arr[mid]) {
    return binarySearch(arr, target, mid + 1, end);
  } else {
    return binarySearch(arr, target, start, mid - 1);
  }
  return -1;
}

采用非递归方式，算法复杂度：最佳情况O(logN)、最差情况O(logN)、平均情况O(logN)。

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    var mid = Math.floor((start + end) / 2);
    if (target === arr[mid]) {
      return mid;
    } else if (target > arr[mid]) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

小结#

二分查找是从中间段开始找，所以它的优点是比较次数少，查找速度快，性能较好。其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找方法适用于不经常变动而查找频繁的有序列表。

补充#

如果所查的组数为无序数组呢？那就需要先把数组重新排序，然后再进行查找。代码演示如下：

function binarySearch(arr, target) {
  // 可以先采用冒泡排序先给数组排序
  let len = arr.length;
  let temp;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  // 排序后再进行查找
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (target === arr[mid]) {
      return mid;
    } else if (target > arr[mid]) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}