二分查找只有一个思想，那就是：逐步缩小搜索区间。

• 原来写过一篇二关于二分法的模板，但是在后面的题目练习中，总感觉对二分法的理解还是差那么点意思。
• 总结的模板根本就没有办法解决题目，经过学习对比后，发现写二分法的重点从来就不在于使用的是哪一个模板（所有模板的背后逻辑都是一样的），更不在于设置的区间是左闭右闭还是左闭右开。而是在于认真看懂题目，根据题目描述的条件和要求思考清楚如何缩减区间，清楚的知道每一轮在什么条件下，搜索的范围是什么，从而设置左边界和有边界。
• 需要分析清楚题目的意思，分析清楚要找的答案需要满足什么性质。应该清楚模板具体的用法，明白需要根据题意灵活处理、需要变通的地方，不可以认为每一行代码都是模板规定死的写法，不可以盲目套用、死记硬背。

二分法只有一个思想：逐步缩小搜索空间！

使用 left 和 right 向中间靠拢的方法，有一个非常强的语义，那就是：当 left 与 right 重合的时候，我们就找到了问题的答案，使用这种写法有一个巨大的好处，那就是返回值不需要考虑返回 left 还是 right，因为退出循环以后，它们是重合的。

在做题的过程中，会遇到两个难点：1、取 mid 的时候，有些时候需要 +1，这是因为需要避免死循环；2、只把区间分成两个部分，这是因为：只有这样，退出循环的时候才有 left 与 right 重合，我们才敢说，找到了问题的答案。（这两个难点，在练习的过程中，会逐渐清晰，不用着急一下子搞懂，事实上并不难理解）。

力扣 35. 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        //二分：找出第一个大于等于target的位置，即为答案
        int n = nums.length;
        int left = 0, right = n;
        //上面right 取到 n 并不是因所谓左闭右开，是因为数组长度n本就可能成为答案：
        //目标元素严格大于输入数组的最后一个元素，答案即为最后一个元素的下标+1，即n
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
             // mid的右侧一定不存在第一个大于等于target的值
             // mid有可能是第一个大于等于target数的位置
             // 下一轮搜索的区间是 [left..mid]
                right = mid;
            } else {
             // mid的左侧一定不存在第一个大于等于target的值
             // num[mid] < target, mid 也不会是第一个大于等于target的位置
             // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            }
        }
        return right;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        //二分，找到第一个大于target的数字
        return getFirstBigger(nums, target) - getFirstBigger(nums, target - 1);
    }
    //返回第一个大于target的数字的位置。
    public int getFirstBigger(int[] nums, int tar) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > tar) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution {
    public int missingNumber(int[] nums) {
        //左子数组均满足nums[i]=i;
        //右子数组均 nums[i] != i;
        //找到右子数组的首个元素。
        int n = nums.length;
        int left = 0, right = n-1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == mid) {
                //mid左边一定不会有目标元素
                //mid也不会是目标元素的位置
                left = mid + 1;
            } else {
                //mid右边一定不会有目标元素
                //mid有可能是右子数组的首元素位置
                right = mid;
            }
        }
        return nums[right] == right? n : right;
    }
}