二分查找

适用场景

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

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

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

3 个二分查找模板

第一个模板

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

    return -1
};

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

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