二分查找并不简单，KMP发明人之一Knuth都说二分查找：思路很简单，细节是魔鬼。二分查找里真正的坑不是整型溢出的bug，而是在于到底要给 mid 加一还是 减一，while 里到底用 <= 还是 <。

框架如下：

分析二分查找的一个技巧是：不要出现else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

其中 …… 的部分，就是可以能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。

计算mid时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

一、寻找一个数（基本的二分搜索）

这个场景是最简单的，搜索一个数，如果存在，返回其索引，否则返回-1。

此算法有什么缺陷？

nums = [1,2,2,3]，target 为 2，此算法返回的索引是2。

但如果想得到 target 的左侧边界，即索引 1，或者target的右侧边界，索引为3，此算法不能直接处理，虽然可以找到一个target，然后向左或者向右线性搜索，但这样就难以保证二分查找对数级的复杂度了。

二、寻找左侧边界的二分搜索

1. 为什么该算法能够搜索左侧边界？

①当nums[mid] > target 或 nums[mid] < target

    和普通二分查找一样，还在逼近target

②当nums[mid] == target

    找到target，但无法确定就是最左的target。

    将当前找到的target及其右侧区间斩去：

    1) 斩去target及右侧后，左边区间内还有target：

        相当于回到 ① ，只是搜索区间变小了，又要重新逼近target，直到nums[mid] 再次等于 target；不断循环，斩去右侧，直到——

    2) 斩去target及右侧后，左边区间内不再有target：

        说明刚才找到的 target 就是最左的target，也就是right。

        当target > nums[right -1] 时，二分查找不断舍弃左边区间，最后left = right时退出while循环，这时的 right 就是一开始的 right;

        反之，当target < nums[0]时，二分查找不断舍弃右边区间，最后right = left时退出while循环，这时的 left 就是一开始 0。

        所以当退出while循环，如果是已经找到target的情况，此时返回的 right = left = 找到最左target 时的 mid。

2. 为什么 while 条件是 left  < right，而不是 left <= right ？

注意到 right 是 nums.length 而不是 nums.length -1，所以查找的区间应该是 [left, right)，否则右侧数组会越界。

while(left < right) 终止条件是 left == right，此时搜索区间 [left, right) 为空，所以可以正确终止。

3. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

对于这个数组，算法会返回1，可以解读为 nums 中小于 2 的元素有 1 个；

对于 nums = [2,3,5,7]，target = 1，算法会返回 0，含义是 nums 中小于 1 的元素有 0 个；

对于 nums = [2,3,5,7]，target = 8，算法会返回 4，含义是 nums 中小于 8 的元素有 4 个。

所以简单添加两行代码就能在正确的时候 return -1：

4. 为什么返回 left 而不是 right？

都是一样的，因为 while 终止的条件是 left == right。

5.能不能把 right 变成 nums.length - 1， 也就是继续使用两边都闭的「搜索区间」？这样就可以和基础二分搜索统一起来。

当然可以，只要「搜索区间」和搜索方式能够避免漏掉元素，随便怎么改都可以。

因为 right 初始化为 nums.length -1，那么 while的终止条件应该是 left == right +1, 也就是while 条件应该用 left <= right：

因为搜索区间是两端都闭的，且现在是搜索左侧边界，所以 left 和 right 的更新逻辑如下：

返回 -1 的情况：

完整代码如下：

这样就和普通版二分搜索算法统一了，都是两端都闭的「搜索区间」。

三、寻找右侧边界的二分查找

同理：

四、总结

通过本文，你得到了：

1. 分析二分查找代码时，不要出现else，全部展成 else if 方便理解

2. 注意「搜索区间」和 while 的终⽌条件，如果存在漏掉的元素，记得在最后检查。

3. 如需定义左闭右开的「搜索区间」搜索左右边界，只要在 nums[mid] == target时做修改即可，搜索右侧时需要减一。

4. 如果将「搜索区间」全部统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可。