二分查找的要点，区间能缩小为一个点

二分查找的要点就是让目标区间不断缩小直至为一个点。

这同样是一些分治算法的目标，比如快速排序，我们的目标是区间缩小为一个点，如果你不能理解这个问题，那么通常会在剩余最后两三个数的时候混乱。

我们在二分查找的时候，要不断通过left right mid的更新去达到我们最终目标；

如果我们的mid计算方式为mid = left + (right - left) / 2;

那么为了能使目标区间最终能缩小为一个点，我们在更新left的时候，至少要让left前进一步，也就是left = mid + 1。

为什么？如果更新算法是left = mid，那么当left + 1 = right;时，会进入死循环，因为相邻两个数字相加除以2得到的mid=left，这时如果更新left=mid，就会进入死循环。

而right则没有这个问题，更新right时，无论是right = mid，还是right = mid - 1，区间最终都会缩小为一个点。

如果因为题目限制，我们必须要让left=mid去更新，那么我们此时必须通过其他的mid计算方式，去避免这个问题。

我们来看两个二分查找的经典题目。

    int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (guess(mid) <= 0) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/guess-number-higher-or-lower/solution/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/first-bad-version/solution/di-yi-ge-cuo-wu-de-ban-ben-by-leetcode-s-pf8h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。