二分查找

区间类型决定终止条件和右边界的移动。

二分查找的关键在于理清楚区间的定义。到底是left < right还是left <= right是在写二分法的时候经常弄不清楚的点，导致一看就会、一写就废。所以首先分析一下这两种循环终止条件有什么不同。

left <= right使用的是一个左闭右闭的区间，即left == right的情况是可能出现并且有意义的。所以当nums[middle] > target的时候，right应当被赋值为middle - 1。因为在左闭右闭的区间中，nums[middle]的值一定不会是target。

而left < right使用的是一个左闭右开的区间，left == right是不会出现的。当nums[middle] > target的时候，right应该被赋值为middle，因为在左闭右开的区间中，不能确保nums[middle]的值与target是否相等。

如果实在难以区分，按照区间左右边界统一的移动原则，可以只记住闭区间这一种写法。

参考代码：

function search (nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        // 为了防止栈溢出采用的写法，和Math.floor((left + right) / 2)是一样的效果。
        let middle = left + Math.floor((right - left) / 2)
        if (nums[middle] > target) {
            right = middle - 1
        } else if (nums[middle] < target) {
            left = middle + 1
        } else {
            return middle
        }
    }
    return -1
}