二分查找的原理很容易理解，但是二分查找就像茴香豆的 hui，有很多种写法，每种都需要仔细地处理各种边界条件，一不小心就会让人调试到头晕，变成时间黑洞，吸光热情和精力。

今天的每日一题又遇到了，是时候拿出我压箱底的模板了。

一个万能二分查找模板

给定一个单调不减数组 arr，和一个数 x，那么用下面的代码模板，可以查找出满足条件 arr[i] >= x 的最小 i：

class Solution {

    /**
     * 二分查找万能模板。 arr 是单调不减数组。
     * 如果返回值等于 arr.length，代表 arr 中不存在 满足 arr[i] >= x 的 i，所有元素都小于 x。
     * 否则返回满足 arr[i] >= x 的最小 i（最左 i）。也就是说，如果有多个连续的 x，会返回最靠左的那个的下标。
     * @param arr 单调不减数组
     * @param x 边界值
     * @return
     */
    public int binarySearch(int [] arr, int x) {
        int l = 0, r = arr.length - 1; // 二分查找的左右初始边界
        while(l <= r){ // 注意这里不是 l < r
            int m = l + (r - l)/2;
            if(arr[m] >= x)r = --m;
            else l = ++m;
        }
        return l; // 此时，l 代表arr[i] >= x 的最小 i。
    }
}

之所以敢称这个模板是万能的，是因为它可以被灵活地调用，实现各种需求：

1. 查找某个数 x 首次出现的位置，如果不存在，返回 -1。如果 binarySearch(arr, x) == arr.length，代表所有元素都小于 x，不存在这样的位置；如果有多个元素等于 x，则binarySearch(arr, x)代表首个 x 的下标；如果arr[binarySearch(arr, x)] != x，则不存在某个数等于 x，binarySearch(arr, x)代表最靠左的大于 x 的数。
2. 查找某个数 x 最后出现的位置，如果不存在，返回 -1。转换为用 int ret = binarySearch(arr, x + 1) - 1 来解决。 如果ret < 0，返回 -1；否则，如果arr[ret] == x，ret 就是答案；否则，返回 -1。
3. 查找某个数 x 首次出现的位置，如果不存在 x，则求出适合插入 x 的位置。binarySearch(arr, x)就是。
4. 查找小于x的最后一个数。转换为用binarySearch(arr, x) - 1来解决。
5. 查找小于x的第一个数。这是个伪问题。
6. 查找大于x的第一个的数。转换为用binarySearch(arr, x + 1)来解决。
7. 查找大于x的最后一个的数。这是个伪问题。

如果把被查找的数组换成单调不增的，可以调整这个模板中的第五行中的 if 条件，把大于等于改为小于等于。

如果解二分查找的题比较耗时间，那么，从现在开始，把这个模板焊死在大脑里，并且找 10 道题练习一下，比如今天的每日一题（戳文末的图片可以看到）。

如果在本文发现错漏，或者有更好的思路，或者有任何疑问，欢迎评论区交流。也可以点个赞支持一下作者🙃🙃~~

今天肝了三个小时写的题解，瞬间沉了下去，很无奈，我需要你的👍🤣