适用场景

二分查找描述了在有序集合中搜索特定值的过程。

成功的二分查找的 3 个部分

预处理 —— 如果集合未排序，则进行排序。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
后处理 —— 在剩余空间中确定可行的候选者。

3 个二分查找模板

第一个模板

  1. var search = function(nums, target) {
  2.     // 区间 [l, r)
  3.     let left = 0, right = nums.length;
  4.     while(left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  5.         let mid = Math.floor((left + right) / 2); // 防止溢出
  6.         if(nums[mid] === target) {
  7.             return mid; // 找到目标值，返回下标
  8.         } else if(nums[mid] > target) {
  9.             right = mid; // target 在左区间，所以[left, mid)
  10.         } else if(nums[mid] < target) {
  11.             left = mid + 1; // target 在右区间，所以[mid + 1, right)
  12.         }
  13.     }
  15.     return -1
  16. };

关键属性
二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

区分语法
初始条件：left = 0, right = length-1
终止：left > right
向左查找：right = mid-1
向右查找：left = mid+1