When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases.
这行代码是有问题的，在
left
和
right
都比较大的时候，
left + right
很有可能超过 int 类型能表示的最大值，即整型溢出，为了避免这个问题，应该写成：
intmid = left + (right - left) / 2 ;
事实上，
int mid = left + (right - left) / 2
在
right
很大、
left
是负数且很小的时候，
right - left
也有可能超过
int
类型能表示的最大值，只不过一般情况下
left
和
right
表示的是数组索引值，
left
是非负数，因此
right - left
溢出的可能性很小。
更好的写法是：
intmid = (left + right) >>> 1 ;
原因在后文介绍，请读者留意：
使用“左边界索引 + 右边界索引”，然后“无符号右移 1 位”是推荐的写法。
（2）循环可以进行的条件写成 while (left <= right) 时，在退出循环的时候，需要考虑返回 left 还是 right，稍不注意，就容易出错
以本题（LeetCode 第 35 题：搜索插入位置）为例。
分析：根据题意并结合题目给出的 4 个示例，不难分析出这个问题的等价表述如下：
说明
：
1、当把二分查找法的循环可以进行的条件写成
while (left <= right)
时，在写最后一句
return
的时候，如果不假思索，把左边界
left
返回回去，虽然写对了，但可以思考一下为什么不返回右边界
right
呢？
2、但是事实上，返回
left
是有一定道理的，如果题目换一种问法，你可能就要返回右边界
right
，这句话不太理解没有关系，我也不打算讲得很清楚（在上面代码的注释中我已经解释了原因），因为实在太绕了，这不是我要说的重点。
由此，我认为“传统二分查找法模板”使用的痛点在于：
传统二分查找法模板，当退出
while
循环的时候，在返回左边界还是右边界这个问题上，比较容易出错。
那么，是不是可以回避这个问题呢？答案是肯定的，答案就在下面我要介绍的“神奇的”二分查找法模板里。
4、“神奇的”二分查找法模板的基本思想
（1）首先把循环可以进行的条件写成
while(left < right)
，
在退出循环的时候，一定有
left == right
成立，此时返回
left
或者
right
都可以
或许你会问：退出循环的时候还有一个数没有看啊（退出循环之前索引 left 或 索引 right 上的值）？
没有关系，我们就等到退出循环以后来看，甚至经过分析，有时都不用看，就能确定它是目标数值。
（什么时候需要看最后剩下的那个数，什么时候不需要，会在第 5 点介绍。）
更深层次的思想是“夹逼法”或者称为“排除法”。
（2）“神奇的”二分查找法模板的基本思想（特别重要）
publicintsearchInsert(int[] nums, int target) { int len = nums.length; if (len == 0) { return-1; } if (nums[len - 1] return len; } int left = 0; int right = len - 1; while (left int mid = left + (right - left) / 2; if (nums[mid] // nums[mid] 的值可以舍弃 left = mid + 1; } else { // nums[mid] 不能舍弃 right = mid; } } return right; }
实现
int sqrt(int x)
函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
分析：因为题目中说“返回类型是整数，结果只保留整数的部分，小数部分将舍被去”。例如
5
的平方根约等于 2.236，在这道题应该返回
2
。因此如果一个数的平方小于或者等于 x，那么这个数有可能是也有可能不是 x 的平方根，但是能很肯定的是，如果一个数的平方大于 x ，这个数肯定不是 x 的平方根。
注意：先写“好想”的分支，排除了中位数之后，通常另一个分支就不排除中位数，而不必具体考虑另一个分支的逻辑的具体意义，且代码几乎是固定的。
while left # 不妨先写左中位数，看看你的分支会不会让你代码出现死循环，从而调整 mid = left + (right - left) // 2 # 业务逻辑代码 if (check(mid)): # 选择右边界的时候，可以排除中位数 right = mid - 1 else: # 选择左边界的时候，不能排除中位数 left = mid
在区间中的元素只剩下 $2$ 个时候，例如：
left = 3
，
right = 4
。此时左中位数就是左边界，如果你的逻辑执行到
left = mid
这个分支，且你选择的中位数是左中位数，此时左边界就不会得到更新，区间就不会再收缩（理解这句话是关键），从而进入死循环；
为了避免出现死循环，你需要选择中位数是右中位数，当逻辑执行到
left = mid
这个分支的时候，因为你选择了右中位数，让逻辑可以转而执行到
right = mid - 1
让区间收缩，最终成为 1 个数，退出
while
循环。
int mid = (left + right) / 2;
的问题：在
left
和
right
很大的时候，
left + right
会发生整型溢出，变成负数，这是一个 bug ，得改！
int mid = left + (right - left) / 2;
在
right
很大、
left
是负数且很小的时候，
right - left
也有可能超过 int 类型能表示的最大值，只不过一般情况下
left
和
right
表示的是数组索引值，
left
是非负数，因此
right - left
溢出的可能性很小。因此，它是正确的写法。下面介绍推荐的写法。
int mid = (left + right) >>> 1;
如果这样写
，
left + right
在发生整型溢出以后，会变成负数，此时如果除以
2
，
mid
是一个负数，但是经过无符号右移，可以得到在不溢出的情况下正确的结果。
解释“无符号右移”：在 Java 中，无符号右移运算符
>>>
和右移运算符
>>
的区别如下：
