本文介绍了我这半年以来，在刷题过程中使用“二分查找法”刷题的一个模板，包括这个模板的优点、使用技巧、注意事项、调试方法等。虽说是模板，但我不打算一开始就贴出代码，因为这个模板根本没有必要记忆，只要你能够理解文中叙述的知识点和注意事项，并加以应用（刷题），相信你会和我一样喜欢这个模板，并且认为使用它是自然而然的事情。
这个模板应该能够帮助你解决 LeetCode 带“二分查找”标签的常见问题（简单、中等难度）。
下面的动画以 「力扣」第 704 题：二分查找 为例，展示了我写二分查找法的一般流程。
binary-search-template.gif
（温馨提示：右键，在弹出的下拉列表框中选择“在新标签页中打开图片”，可以查看大图。）
image.png
历史上，二分查找算法虽然思想简单，但引起了人们的足够重视和关注。
1、算法和程序设计技术的先驱 Donald Ervin Knuth（中文名：高德纳）：
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky ...
译：“虽然二分查找的基本思想相对简单，但细节可能会非常棘手”。来自维基百科 Binary_search_algorithm，请原谅本人可能非常不优雅的中文翻译。
2、同样是高德纳先生，在其著作《计算机程序设计的艺术 第3卷：排序和查找》中指出：
二分查找法的思想在 1946 年就被提出来了。但是第 1 个没有 Bug 的二分查找法在 1962 年才出现。
（因为时间和能力的关系，原谅我没有办法提供英文原文，如果能找到英文原文的朋友欢迎提供一下出处，在此先谢过。）
据说这个 Bug 在 Java 的 JDK 中都隐藏了将近 10 年以后，才被人们发现并修复。
3、《编程珠玑》的作者 Jon Bentley：
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.
译：当 JonBentley 把二分查找作为专业程序员课程中的一个问题时，他发现百分之九十的人在花了几个小时的时间研究之后，没有提供正确的解决方案，主要是因为错误的实现无法正确运行（笔者注：可能返回错误的结果，或者出现死循环），或者是不能很好地判断边界条件。
我最早学习的二分查找法分为递归版本和非递归版本：
- 递归版本（这段代码有毒，不要记它）
传统二分查找法模板-1.png
- 非递归版本（这段代码有毒，不要记它）
传统二分查找法模板-2.png
说明：上面这两段代码是我建议你忘掉的，我最后给出的代码我也不建议你记住，理解并应用它就可以了。它们都可以直接完成二分查找算法的模板题：「力扣」第 704 题：二分查找。
下面，我们使用这个模板完成一下本题（「力扣」第 35 题：搜索插入位置）。
分析：根据题意并结合题目给出的 4 个示例，不难分析出这个问题的等价表述如下：
1、如果目标值（严格）大于排序数组的最后一个数，返回这个排序数组的长度，否则进入第 2 点。
2、返回排序数组从左到右，大于或者等于目标值的第 1 个数的索引。
事实上，当给出数组中有很多数和目标值相等的时候，我们返回任意一个与之相等的数的索引值都可以，不过为了简单起见，也为了方便后面的说明，我们返回第 1 个符合题意的数的索引。
题目告诉你“排序数组”，其实就是在疯狂暗示你用二分查找法。 二分查找法的思想并不难，但写好一个二分法并不简单，下面就借着这道题为大家做一个总结。
一、传统二分查找法模板
binary-search-template-1.png
刚接触二分查找法的时候，使用上面的模板，我们可能会像下面这样写代码，我把这种写法容易出错的地方写在了注释里：
参考代码：针对本题（LeetCode 第 35 题）
public class Solution3 {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (nums[len - 1] < target) {
return len;
}
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
// 等于的情况最简单，我们应该放在第 1 个分支进行判断
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 题目要我们返回大于或者等于目标值的第 1 个数的索引
// 此时 mid 一定不是所求的左边界，
// 此时左边界更新为 mid + 1
left = mid + 1;
} else {
// 既然不会等于，此时 nums[mid] > target
// mid 也一定不是所求的右边界
// 此时右边界更新为 mid - 1
right = mid - 1;
}
}
// 注意：一定得返回左边界 left，
// 如果返回右边界 right 提交代码不会通过
// 【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
// 但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论
// 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
// 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
// 根据题意应该返回 left，
// 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
return left;
}
}
说明：
1、当你把二分查找法的循环可以进行的条件写成 while (left <= right) 的话，在写最后一句 return 的时候，如果你不假思索，把左边界 left 返回回去，你写对了，但为什么不返回右边界 right 呢？
2、但是事实上，返回 left 是有一定道理的，如果题目换一种问法，你可能就要返回右边界 right，这句话不太理解没有关系，我也不打算讲得很清楚（在上面代码的注释中我已经解释了原因），因为实在太绕了，这不是我要说的重点。
由此，我认为“传统二分查找法模板”使用的痛点在于：
传统二分查找法模板，当退出
while循环的时候，在返回左边界还是右边界这个问题上，比较容易出错。
那么，是不是可以回避这个问题呢？答案是肯定的，答案就在下面我要介绍的“神奇的”二分查找法模板里。
二、“神奇的”二分查找法模板
binary-search-template-2.png
binary-search-template-3.png
二分查找法的思想：二分查找法的思想是“夹逼”，或者说“排除”，而“二分”只是手段，即“通过二分排除了候选区间的一大半的非目标元素”。具体说来，如下：
在每一轮循环中，都可以排除候选区间里将近一半的元素，进而使得候选区间越来越小，直至有限个数（通常为
个），而这个数就有可能是我们要找的数（在一些情况下，还需要单独做判断）。
下面我要介绍的“神奇的”二分查找法模板，就把这个思想发挥到了极致。
在一些资料中，你可能看过别人写二分查找法，把循环可以进行的条件写成 while (left < right) ，当时你是不是跟我一样有疑问：“咦？当左右边界一样的时候，那个数岂不是会被漏掉”。但是我要告诉你，这样写在绝大多数情况下是最好的，这也是“神奇的”二分查找法模板好用的一部分。
理由很简单：写 while (left < right) 的时候，退出循环时，左边界等于右边界，因此你不必纠结要返回 left 还是 right ，此时返回 left 或者 right 都是可以的。
二分查找法之所以高效，是因为它利用了数组有序的特点，在每一次的搜索过程中，都可以排除将近一半的数，使得搜索区间越来越小，直到区间成为一个数。回到这一节最开始的疑问：“区间左右边界相等（即收缩成 1 个数）时，这个数是否会漏掉”，解释如下：
1、如果你的业务逻辑保证了你要找的数一定在左边界和右边界所表示的区间里出现，那么可以放心地返回 l 或者 r，而无需再做判断；
2、如果你的业务逻辑不能保证你要找的数一定在左边界和右边界所表示的区间里出现，那么只要在退出循环以后，再针对 nums[left] 或者 nums[right] （此时 nums[left] == nums[right]）单独作一次判断，看它是不是你要找的数即可，这一步操作常常叫做“后处理”。
阶段总结：
加上了对候选区间是否存在目标元素的思考和判断，写
while (left < right)这个逻辑就可以避免你对返回左边界还是右边界的讨论。
下面给出这道问题，使用 while (left < right) 模板写法的 2 段参考代码，以下代码的细节部分在后文中会讲到，因此一些地方不太明白没有关系，暂时跳过即可。
参考代码 1：重点理解为什么候选区间的索引范围是 [0, size]。
from typing import List
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 返回大于等于 target 的索引，有可能是最后一个
size = len(nums)
# 特判
if size == 0:
return 0
left = 0
# 如果 target 比 nums里所有的数都大，则最后一个数的索引 + 1 就是候选值，因此，右边界应该是数组的长度
right = size
# 二分的逻辑一定要写对，否则会出现死循环或者数组下标越界
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
assert nums[mid] >= target
# [1,5,7] 2
right = mid
# 调试语句
# print('left = {}, right = {}, mid = {}'.format(left, right, mid))
return left
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
参考代码 2：对于是否接在原有序数组后面单独判断，不满足的时候，再在候选区间的索引范围 [0, size - 1] 内使用二分查找法进行搜索。
from typing import List
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 返回大于等于 target 的索引，有可能是最后一个
size = len(nums)
# 特判 1
if size == 0:
return 0
# 特判 2：如果比最后一个数字还要大，直接接在它后面就可以了
if target > nums[-1]:
return size
left = 0
right = size - 1
# 二分的逻辑一定要写对，否则会出现死循环或者数组下标越界
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
assert nums[mid] >= target
right = mid
return left
public class Solution {
// 只会把比自己大的覆盖成小的
// 二分法
// 如果有一连串数跟 target 相同，则返回索引最靠前的
// 特例： 3 5 5 5 5 5 5 5 5 5
// 特例： 3 6 7 8
// System.out.println("尝试过的值：" + mid);
// 1 2 3 5 5 5 5 5 5 6 ，target = 5
// 1 2 3 3 5 5 5 6 target = 4
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
if (nums[len - 1] < target) {
return len;
}
int left = 0;
int right = len - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// nums[mid] 的值可以舍弃
left = mid + 1;
} else {
// nums[mid] 不能舍弃
right = mid;
}
}
return right;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6};
int target = 4;
Solution2 solution2 = new Solution2();
int searchInsert = solution2.searchInsert(nums, target);
System.out.println(searchInsert);
}
}
当然，这段代码你可能看得还是云里雾里，不过别急，我马上为你道来其中的玄机。
三、技巧、调试方法和注意事项
1、先来看 int mid = left + (right - left) / 2; 这句代码，这就是对文章一开始所说的那个在 Java 的 JDK 中被人们忽视了将近 10 年的 Bug 的修复：
（1）当 left 和 right 是很大的整数的时候，如果写 int mid = (left + right) / 2; 这里 left + right 的值就有可能超过 int 类型能表示的最大值，因此使用 mid = left + (right - left) // 2 可以避免这种情况。
（2）事实上，mid = left + (right - left) // 2 在 right 很大、 left 是负数且很小的时候， right - left 也有可能超过 int 类型能表示的最大值，只不过一般情况下 left 和 right 表示的是数组索引值，left 是非负数，因此 right - left 溢出的可能性很小。
2、当数组的元素个数是偶数的时候，中位数有左中位数和右中位数之分：
（1）当数组的元素个数是偶数的时候：
-
使用
mid = left + (right - left) // 2得到左中位数的索引； -
使用
mid = left + (right - left + 1) // 2得到右中位数的索引。
（2）当数组的元素个数是奇数的时候，以上二者都能选到最中间的那个中位数。
事实上，这不是什么特别难想的事情，我们只要使用一个具体的例子来验证即可：当左边界索引 left = 3，右边界索引 right = 4 的时候，
mid1 = left + (right - left) // 2 = 3 + (4 - 3) // 2 = 3 + 0 = 3，
mid2 = left + (right - left + 1) // 2 = 3 + (4 - 3 + 1) // 2 = 3 + 1 = 4。
左中位数 mid1 是索引 left，右中位数 mid2 是索引 right。
记忆方法：
(right - left)不加
那么，什么时候使用左中位数，什么时候使用右中位数呢？选中位数的依据是为了避免死循环，得根据分支的逻辑来选择中位数，而分支逻辑的编写也有技巧，下面展开来说。
3、编写分支逻辑的时候，先写“排除逻辑”所在的分支。
binary-search-template-4.png
这里介绍很重要的一个技巧：先考虑能把“中位数”排除在外的逻辑，而不能排除“中位数”的逻辑放在 else 分支里，这样做的理由有 2 点：
（1）可以排除“中位数”的逻辑，通常比较好想，但并不绝对，这一点视情况而定；
（2）分支条数变成 2 条，比原来 3 个分支要考虑的情况少，好处是：
不用在每次循环开始单独考虑中位数是否是目标元素，节约了时间，我们只要在退出循环的时候，即左右区间压缩成一个数（索引）的时候，去判断这个索引表示的数是否是目标元素，而不必在二分的逻辑中单独做判断。
这一点很重要，希望读者结合具体练习仔细体会，每次循环开始的时候都单独做一次判断，在统计意义上看，二分时候的中位数恰好是目标元素的概率并不高，并且即使要这么做，也不是普适性的，不能解决绝大部分的问题。
以本题为例，通过之前的分析，我们需要找到“大于或者等于目标值的第 1 个数的索引”。对于这道题而言：
（1）如果中位数小于目标值，它就应该被排除，左边界 left 就至少是 mid + 1；
（2）如果中位数大于等于目标值，还不能够肯定它就是我们要找的数，因为要找的是等于目标值的第 个数的索引，中位数以及中位数的左边都有可能是符合题意的数，因此右边界就不能把
mid 排除，因此右边界 right 至多是 mid，此时右边界不向左边收缩。
下一点就更关键了。
4、根据分支编写的情况，选择使用左中位数还是右中位数。
binary-search-template-5.png
binary-search-template-6.png
先写分支，根据分支的逻辑选中位数，选左中位数还是右中位数，这要做的理由是为了防止出现死循环。
死循环容易发生在区间只有
个元素时候，此时中位数的选择尤为关键。
选择中位数的依据：为了避免出现死循环，我们需要确保：
（下面的这两条规则说起来很绕，可以暂时跳过，不要去记它，我写的时候都晕）。
1、如果分支的逻辑，在选择左边界的时候，不能排除中位数，那么中位数就选“右中位数”，只有这样区间才会收缩，否则进入死循环；
2、同理，如果分支的逻辑，在选择右边界的时候，不能排除中位数，那么中位数就选“左中位数”，只有这样区间才会收缩，否则进入死循环。
理解上面的这个规则可以通过具体的例子。针对以上规则的第 1 点：如果分支的逻辑，在选择左边界的时候不能排除中位数，例如：
Python 伪代码：
while left < right:
# 不妨先写左中位数，看看你的分支会不会让你代码出现死循环，从而调整
mid = left + (right - left) // 2
# 业务逻辑代码
if (check(mid)):
# 选择右边界的时候，可以排除中位数
right = mid - 1
else:
# 选择左边界的时候，不能排除中位数
left = mid
-
在区间中的元素只剩下
left = 3，right = 4。此时左中位数就是左边界，如果你的逻辑执行到left = mid这个分支，且你选择的中位数是左中位数，此时左边界就不会得到更新，区间就不会再收缩（理解这句话是关键），从而进入死循环； - 为了避免出现死循环，你需要选择中位数是右中位数，当逻辑执行到
left = mid这个分支的时候，因为你选择了右中位数，让逻辑可以转而执行到right = mid - 1让区间收缩，最终成为 1 个数，退出while循环。
上面这段话不理解没有关系，因为我还没有举例子，你有个印象就好，类似地，理解选择中位数的依据的第 2 点。
5、当出现死循环的时候的调试方法：打印输出左右边界、中位数的值和目标值、分支逻辑等必要的信息。
binary-search-template-9.png
按照我的经验，一开始编码的时候，稍不注意就很容易出现死循环，不过没有关系，你可以你的代码中写上一些输出语句，就容易理解“在区间元素只有 2 个的时候容易出现死循环”。具体编码调试的细节，可以参考我在「力扣」第 69 题：x 的平方根的题解《二分查找 + 牛顿法（Python 代码、Java 代码）》 。
四、使用总结
总结一下，我爱用这个模板的原因、技巧、优点和注意事项：
1、原因：
无脑地写
while left < right:，这样你就不用判断，在退出循环的时候你应该返回left还是right，因为返回left或者right都对；
2、技巧：
先写分支逻辑，并且先写排除中位数的逻辑分支（因为更多时候排除中位数的逻辑容易想，但是前面我也提到过，这并不绝对），另一个分支的逻辑你就不用想了，写出第 1 个分支的反面代码即可（下面的说明中有介绍），再根据分支的情况选择使用左中位数还是右中位数；
说明：这里再多说一句。如果从代码可读性角度来说，只要是你认为好想的逻辑分支，就把它写在前面，并且加上你的注释，这样方便别人理解，而另一个分支，你就不必考虑它的逻辑了。有的时候另一个分支的逻辑并不太好想，容易把自己绕进去。如果你练习做得多了，会形成条件反射。
我简单总结了一下，左右分支的规律就如下两点：
-
如果第 1 个分支的逻辑是“左边界排除中位数”（
left = mid + 1），那么第 2 个分支的逻辑就一定是“右边界不排除中位数”（right = mid），反过来也成立； -
如果第 2 个分支的逻辑是“右边界排除中位数”（
right = mid - 1），那么第 2 个分支的逻辑就一定是“左边界不排除中位数”（left = mid），反之也成立。
“反过来也成立”的意思是：如果在你的逻辑中，“边界不能排除中位数”的逻辑好想，你就把它写在第 1 个分支，另一个分支是它的反面，你可以不用管逻辑是什么，按照上面的规律直接给出代码就可以了。能这么做的理论依据就是“排除法”。
在「力扣」第 287 题：寻找重复数的题解《二分法（Python 代码、Java 代码）》和这篇题解的评论区中，有我和用户
@fighterhit 给出的代码，在一些情况下，我们先写了不排除中位数的逻辑分支，更合适的标准就是“哪个逻辑分支好想，就先写哪一个”，欢迎大家参与讨论。
3、优点：
分支条数只有 2 条，代码执行效率更高，不用在每一轮循环中单独判断中位数是否符合题目要求，写分支的逻辑的目的是尽量排除更多的候选元素，而判断中位数是否符合题目要求我们放在最后进行，这就是第 5 点；
说明：每一轮循环开始都单独判断中位数是否符合要求，这个操作不是很有普适性，因为从统计意义上说，中位数直接就是你想找的数的概率并不大，有的时候还要看看左边，还要看看右边。不妨就把它放在最后来看，把候选区间“夹逼”到只剩 个元素的时候，视情况单独再做判断即可。
4、注意事项 1：
左中位数还是右中位数选择的标准根据分支的逻辑而来，标准是每一次循环都应该让区间收缩，当候选区间只剩下
5、注意事项 2：
如果能确定要找的数就在候选区间里，那么退出循环的时候，区间最后收缩成为
binary-search-template-7.png
最后给出两个模板，大家看的时候看注释，不必也无需记忆它们。
二分查找模板-1.png
二分查找模板-2.png
说明：我写的时候，一般是先默认将中位数写成左中位数，再根据分支的情况，看看是否有必要调整成右中位数，即是不是要在 (right - left) 这个括号里面加 。
虽说是两个模板，区别在于选中位数，中位数根据分支逻辑来选，原则是区间要收缩，且不出现死循环，退出循环的时候，视情况，有可能需要对最后剩下的数单独做判断。
我想我应该是成功地把你绕晕了，如果您觉得啰嗦的地方，就当我是“重要的事情说了三遍”吧，确实是重点的地方我才会重复说。当然，最好的理解这个模板的方法还是应用它。在此建议您不妨多做几道使用“二分查找法”解决的问题，用一下我说的这个模板，在发现问题的过程中，体会这个模板好用的地方，相信你一定会和我一样爱上这个模板的。
在「力扣」的探索版块中，给出了二分查找法的 3 个模板，我这篇文章着重介绍了第 2 个模板，但是我介绍的角度和这个版块中给出的角度并不一样，第 1 个模板被我“嫌弃”了，第 3 个模板我看过了，里面给出的例题也可以用第 2 个模板来完成，如果大家有什么使用心得，欢迎与我交流。
五、应用提升
这里给出一些练习题，这些练习题都可以使用这个“神奇的”二分查找法模板比较轻松地写出来，并且得到一个不错的分数，大家加油！
image.png
说明：传送门。这道题是二分查找的模板题，因为目标值有可能在数组中并不存在，所以退出 while 循环的时候，要单独判断一下。
image.png
说明：传送门。
（1）题解链接已经在上文中已经给出，这道题根据分支的逻辑应该选右中位数；
（2）这道题因为还有更高效的“牛顿法”，所以看起来排名并不是特别理想。
image.png
说明：传送门，第 300 题的一个子过程就是本题（第 35 题），我在这道题的题解《动态规划 + 贪心算法（二分法）（Python 代码、Java 代码）》 中给了两个 Python 的示例代码，它们是对本文中给出的注意事项：
如果你确定要搜索的数在区间里，循环完成以后直接返回即可；如果你不确定要搜索的数在区间里，循环完成以后需要再做一次判断。
的具体代码实现。
image.png
说明：传送门，二分查找法还可以用于部分有序数组中元素的查找。
image.png
说明：传送门。
image.png
说明：传送门，这道题是对“数”作二分，而不是对索引做二分，具体可以参考我写的题解《二分法（Python 代码、Java 代码）》。
这里要感谢一下「力扣」的用户 @顾叶峰，他提醒了我“慎用 L 啊，跟 1 傻傻分不清楚了”，根据他的建议，我正在尽力修改以前我写的题解（包括本文）。
image.png
说明：传送门。这道题很有意思，做这一道题等于做了 3 道二分查找的问题，并且，你还会发现，这 3 个二分查找的问题写出来的分支都是一样的，因此它们选中位数的时候，都选择了左中位数。
image.png
说明：传送门。这道题是「力扣」的探索版块里给出了二分查找法的 3 个模板中第 3 个模板的练习题，实际上也可以用我给出的这个模板（即“探索”里面的第 2 个模板）来完成，这道题我也写了题解《排除法（双指针） + 二分法（Python 代码、Java 代码）》。
彩蛋：解释上面的模板中，取中位数的时候为什么使用 ➕且无符号右移
binary-search-template-8.png
以下的文字选自我的博客同名文章的评论，希望对大家有所帮助。
@yangtianrui95
博主您好：
我看到JDK8中计算mid的方法是int mid = (low + high) >>> 1;如果low和high很大的话，请问这个计算会有文章提到的精度溢出问题么？
如果有的话，为啥JDK不用int mid = low + (high-low) >>> 1;这种方法啊？private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) { int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = list.get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found }
谢谢您提了这么好的一个问题，趁着这个机会，我也学习了一下。其实你说的这一点我在文章中有提到：
事实上
mid = l + (r - l) // 2在r很大，并l是负数且很小的时候，r - l也有可能超过 int 类型能表示的最大值，只不过一般情况下l和r表示的是数组索引值，l是非负数，因此r - l溢出的可能性很小。
我再补充说明一下：
1、int mid = (low + high) // 2 与 int mid = low + (high - low) // 2 两种写法都有整型溢出的风险，没有哪一个是绝对安全的，注意：这里我们取平均值用的是除以 2，并且是整除：
-
int mid = (low + high) // 2在low和higt都很大的时候会溢出； -
int mid = low + (high - low) // 2在higt很大，且low是负数且很小的时候会溢出；
2、写算法题的话，一般是让你在数组中做二分查找，因此 low 和 higt 一般都表示数组的索引，因此 low 在绝大多数情况下不会是负数并且很小，因此使用 int mid = low + (high - low) // 2 相对 int mid = (low + high) // 2 更安全一些，并且也能向别人展示我们注意到了整型溢出这种情况，但事实上，我们的考虑还是没有 JDK8 的编写者们深入；
3、至于 JDK8 中采用 int mid = (low + high) >>> 1 这种写法，其实是大有含义的：
JDK8 中采用
int mid = (low + high) >>> 1这种写法，重点不在+，而在>>>。
我们看极端的情况，low 和 high 都是整型最大值的时候，注意，此时 32 位整型最大值它的二进制表示的最高位是 0，它们相加以后，最高位是 1 ，变成负数了，但是再经过无符号右移 >>>（重点是忽略了符号位，空位都以 0 补齐），就能保证使用 + 在整型溢出了以后结果还是正确的。
Java 中 Collections 和 Arrays 提供的 binarySearch 方法，我们点进去看 low 和 high 都表示索引，使用无符号右移又不怕整型溢出，那就用 int mid = (low + high) >>> 1 好啦。位运算本来就比使用除法快，这样看来使用 + 和 <<< 真的是又快又好了。
我想这一点可能是 JDK8 的编写者们更层次的考量。还有一个原因，我觉得是加法比减法可能更快吧，这点或许无足轻重。
看来以后写算法题，就用 int mid = (low + high) >>> 1 吧，反正更多的时候 low 和 high 表示索引，更别人解释的时候更装 ❌ 一些，嘻嘻嘻。
当然以上并不是我想到的，写这篇回答的时候，我参考了以下网络资源，希望也会对你有所帮助，欢迎交流哈。
参考资料 1：https://www.zhihu.com/question/20101702
参考资料 2：https://stackoverflow.com/questions/33616299/java-will-low-high-1-overflow
网友评论