做好总结，胜过脑残机械的刷十道题～ 这算是学习的第一个比较常用的算法，今天总结的是二分法 真的是超级好超级详细超级明白超级实用的二分法总结文章了
我不是总结者，我只是代码的搬运工，觉得写的非常好，作者真的是太赞了，就自己一个个字敲下来了记录下来
作者：liweiwei1419 链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 来源：力扣（LeetCode）
这行代码是有问题的，在left和right比较大的时候，left+right 很有可能超过int类型所能表示的最大值，也就是整形溢出，为了避免这个问题，应该写成：
int mid = left + (left - right ) / 2;事实上，上面的这个式子在right很大、left是负数且很小的时候，right - left也有可能超过int所能表示的最大值，只不过一般情况下，left和right表示的是数组索引值，left-right是非负数，因此left-right溢出的可能性很小。 更好的写法是：
int mid = (left + right) >>> 1; (2)循环可以进行的条件写成while (left <= right)时，在退出循环的时候，需要考虑返回right还是left，稍不留意，就会出错以本题（LeetCode 第 35 题：搜索插入位置）为例。 分析：根据题意并结合题目给出的4个实例，不难分析出这个问题的等价描述如下：
1 如果目标值（严格）大于排序数组的最后一个数，返回这个排序数据的长度，否则进入第2点。 2 返回排序数组从左到右，大于或等于目标值的第1个数的索引。
刚接触二分查找法的时候，我们可能会像下面这样写代码，我把这种写法容易出错的地方写在了注释里： 参考代码：（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; } } 作者：liweiwei1419 链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 来源：力扣（LeetCode）说明：
当把二分查找法的循环可以进行的条件写成 while (left <= right) 时，在写最后一句 return 的时候，如果不假思索，把左边界 left 返回回去，虽然写对了，但可以思考一下为什么不返回右边界 right 呢？ 上面的注释里已经写的很清楚了
因此，“传统的”二分法的痛点在于：
使用二分法查找模版，当退出while循环的时候，在返回左边界还是右边界的问题上，比较容易出错
接下来进入正题正题正题环节了
（什么时候需要看，什么时候不需要看，会在后面的第三点进行介绍）
（2）“神奇的”二分查找模版的基本思想（非常重要）“排除法”即：在每一轮的循环中排除一半以上的元素，对于数级别的时间复杂度内，就可以把区间“夹逼”只剩下1个数，而这个数是不是我们要找的数，单独做一次判断就可以了。
“夹逼法” 或者 “排除法” 是二分查找的基本思想，“二分”是手段，在目标元素不确定的情况下，“二分”也是“最大熵原理”告诉我们的选择
还是 LeetCode 第 35 题，下面给出使用 while (left < right) 模板写法的 2 段参考代码，
参考代码1对于是否接在原有序数组后面单独判断，满足的时候，再在候选区间的索引范围 [0, size ] 内使用二分查找法进行搜索。
public class Solution { public int searchInsert(int[] nums, int target) { int len = nums.length; //特判 if (len == 0) { return 0; } int left = 0; //如果target比nums里的所有数都要大，则最后一个数的索引+1就是候选值，因此，右边界应该是数组的长度 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] 内使用二分查找法进行搜索。 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) { //返回大于等于targrt的索引，有可能是最后一个 int len = nums.length; //特判1 if (len == 0) { return -1; } //特判2:如果比最后一个数字还要大，直接在它后面就行了 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); } }例：LeetCode 第 69 题：x 的平方根 实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 分析：一个非负整数的平方根最小可能是 0 ，最大可能是它自己。 因此左边界可以取 0 ，右边界可以取 x。 可以分析得再细一点，但这道题没有必要，因为二分查找法会帮你排除掉不符合的区间元素。
例：LeetCode 第 287 题：寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 分析：题目告诉我们“其数字都在 1 到 n 之间（包括 1 和n）”。因此左边界可以取 1 ，右边界可以取 n。
要注意2点：
如果left和right表示的是数组的索引，就要考虑“索引是否有效”，即“索引是否越界”是重要的定界依据。左右边界一定要包括目标元素。例如35题，当target比数组中的最后一个数字 还要大（不能等于）的时候，插入元素的位置就是数组的最后一个位置+1，即（len - 1 +1 ）=len,如果忽略这一点，把边界定为len-1，代码就不能通过在线测评。（2） 中位数先写 int mid = (left + right) >>> 1; 根据循环分支的编写情况，再做调整
理解这一点，首先要知道：当数组的元素个数是偶数的时候，中位数有左中位数和右中位数之分。
当数组的元素个数是偶数的时候： 使用int mid = left + (right - left) / 2 ;得到左中位数的索引； 使用int mid = left + (right - left + 1) / 2 ;，得到右中位数的索引；当数组元素的个数是奇数的时候，以上两者都能选到最中间的那个数。其次，
`int mid = left + (right - left) / 2 ;` 等价于 `int mid = (left + right) >>> 1；` `int mid = left + (right - left + 1) / 2 ;` 等价于 `int mid = (left + right + 1) >>> 1` 。我们使用一个例子来验证一下：当左边界索引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） 不加1选左中位数，加1选右中位数
那么，什么时候使用左中位数，什么时候使用右中位数呢？ 选中位数的一句是为了避免死循环，得根据分支的逻辑来判断选择中位数。 分支逻辑编写也有技巧，下面说。
（3） 先写逻辑上容易想到的逻辑分支，这个分支通常是排除中位数的逻辑 在逻辑上 ，“可能是也有可能不是” 让我们感到犹豫不定，但“一定不是”是我们非常坚定的，通常考虑的因素特别单一，因此“好想”。 在生活中，我们会听到这样的话。找对象时，“有车有房可以开绿，但没有一定不要”，就是这种思想的体现。
例：LeetCode 第 69 题：x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
因为题目中说“返回类型是整数，结果只保留整数的部分，小数部分可能被舍去”。例如5的平方根约等于2.236，在这道题中应该返回2。因此如果一个数的平方小于或等于x，那么这个数有可能是也有可能不是x的平方根，但是可以肯定的是，如果一个数的平方大于x，这个数肯定不是x的平方根。
注意：先写“好想的”分支，排除了中位数以后，通常另一个分支就不排除中位数，而不必考虑另一个分支的逻辑的具体意义，且代码几乎是固定的。
（4）循环内只写两个分支，一个分支排除中位数，另一个分支不排除中位数，循环中不单独对中位数做判断 既然是“夹逼法”，没有必要在每一轮开始前单独判断当前中位数是否是目标元素，因此分支数少了一支，代码执行效率更高。
可以排除“中位数”的逻辑，通常比较好想，但是并不绝对，这一点视情况而定。 分支数变成2条，比原来的3个分支要考虑的情况少，好处是：
不用在每次循环开始单独考虑中位数是否是目标元素，节约了时间，我们只要在退出循环的时候，即左右区间压缩成一个数（索引）的时候，去判断这个索引表示的是否是目标元素，而不必在二分的逻辑中作出单独的判断。
这一点很重要，每次循环开始的时候都单独做一次判断，在统计意义上来看，二分的中位数恰好是目标元素的概率并不高，并且即使要那么做，也不是普适性的，不能解决绝大部分的问题。
还以 LeetCode 第 35 题为例，通过之前的分析，我们需要找到“大于或者等于目标值的第 1 个数的索引”。对于这道题而言：
如果中位数小于目标值，它就应该被排除，左边界left就至少是mid+1；如果中位数大于等于目标值，还不能够肯定它就是我们要找的数，因为要找的是等于目标值的第1个数的索引，中位数及中位数的左边可能都是符合题意的数，因此右边界就不能把mid排除，因此右边界right至多是mid，此时右边界不向左边收缩。下一点就更关键了 （5）根据分支逻辑选择中位数的类型，可能是左中位数，也可能是右中位数，选择的标准是避免死循环 死循环容易发生在区间只有2个元素的时候，此时中位数的选择尤为重要。选择中位数的依据是：避免出现死循环。 我们需要确保：
如果分支的逻辑，在选择左边界的时候，不能排除中位数，那么中位数就选“右中位数”，只有这样区间才会收缩，否则进入死循环。同理，如果分支的逻辑，在选择右边界的时候，不能排除中位数，那么中位数就选“左中位数”，只有这样区间才会收缩，否则进入死循环。理解上面的规则可以通过下面的这个具体的例子： 这个例子是针对规则的第一点：如果分支的逻辑，在选择左边界的时候不能排除中位数，例如：
#python伪代码 while left < right: # 不妨先写左中位数，看看你的分支会不会让你代码出现死循环，从而调整 mid = left + (right - left) // 2 # 业务逻辑代码 if (check(mid)): # 选择右边界的时候，可以排除中位数 right = mid - 1 else: # 选择左边界的时候，不能排除中位数 left = mid 在区间的元素只剩下2个的时候，例如：left =3,right=4。此时左中位数就是左边界，如果你的执行逻辑执行到left = mid这个分支，且你选择的中位数是左中位数，此时的左边界就不会得到更新，区间就不会再收缩（理解这句话是关键），从而进入死循环。为了避免出现死循环，你需要选择的中位数是右中位数，当逻辑执行到left = right这个分支的时候，因为你选择了右中位数，让逻辑可以转而执行到right = mid -1，让区间收缩，最终成为一个数，退出while循环。（6）退出循环的时候，可能需要对“夹逼”剩下的那个数单独的做一次判断，这一步称之为“后处理” 二分查找之所以高效，是因为它利用了数组有序的特点，在每一次的搜索过程中，都可以排除将近一半的数，使得搜索区间越来越小，直到区间成为一个数。
回到我们刚开始的疑问，如果“区间左右边界相等（即收缩成1个数）时，这个数是否会漏掉”，解释如下：
如果你的业务逻辑保证了你要找的数一定在左边界和右边界所表示的区间里出现，那么可以放心的返回left或者right，无需判断。如果你的业务逻辑不能保证你要找的数在左边界和右边界所表示的区间里出现，那么只要在退出循环之后，再针对nums[left]或者nums[right]（此时nums[left] == nums[right]）单独做一次判断，看它是不是你要找的数即可，这一步操作常常叫做“后处理”如果你能确定候选区间里目标元素一定存在，则不必做“后处理”。例：LeetCode 第 69 题：x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 分析：非负实数 x 的平方根在 [0, x] 内一定存在，故退出 while (left < right) 循环以后，不必单独判断 left 或者 right 是否符合题意。
如果你不能确定候选区间里目标元素一定存在，需要单独做一次判断。例：LeetCode 第 704 题：二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
分析：因为目标数有可能不在数组中，当候选区间夹逼成一个数的时候，要单独判断一下这个数是不是目标数，如果不是，返回 -1。 （7）取中位数的时候，要避免在计算上出现整型溢出
以后写算法题，就用 int mid = (left + right) >>> 1 吧，反正更多的时候 left 和 right 表示索引。
总结一下，这个模版好用的原因、技巧、优点和注意事项： （1）原因 无脑的写while left <right; 这样你就不用判断，在退出循环的时候是应该返回left还是right，因为两者都对。
（2）技巧
先写分支逻辑，并且先写排除中位数的逻辑分支（因为更多时候排除中位数的逻辑容易想，但是也并不绝对），另一个逻辑分支就不用想了，写成第1个分支的反面代码即可，再根据分支情况选择使用左中位数还是右中位数。 总结一下，左右分支的规律就以下两点：
如果第 1 个分支的逻辑是“左边界排除中位数”（left = mid + 1），那么第 2 个分支的逻辑就一定是“右边界不排除中位数”（right = mid），反过来也成立；如果第 2 个分支的逻辑是“右边界排除中位数”（right = mid - 1），那么第 2 个分支的逻辑就一定是“左边界不排除中位数”（left = mid），反之也成立。“反过来也成立”的意思是：如果在你的逻辑中，“边界不能排除中位数”的逻辑好想，你就把它写在第 1 个分支，另一个分支是它的反面，你可以不用管逻辑是什么，按照上面的规律直接给出代码就可以了。能这么做的理论依据就是“排除法”。
（3）优点 分支条数只有 2 条，代码执行效率更高，不用在每一轮循环中单独判断中位数是否符合题目要求，写分支的逻辑的目的是尽量排除更多的候选元素，而判断中位数是否符合题目要求我们放在最后进行。 说明：每一轮循环开始都单独判断中位数是否符合要求，这个操作不是很有普适性，因为从统计意义上说，中位数直接就是你想找的数的概率并不大，有的时候还要看看左边，还要看看右边。不妨就把它放在最后来看，把候选区间“夹逼”到只剩 1 个元素的时候，视情况单独再做判断即可。 （4）注意事项
左中位数还是右中位数选择的标准根据分支的逻辑而来，标准是每一次循环都应该让区间收缩，当候选区间只剩下 2 个元素的时候，为了避免死循环发生，选择正确的中位数类型。如果你实在很晕，不防就使用有 2 个元素的测试用例，就能明白其中的原因，另外在代码出现死循环的时候，建议你可以将左边界、右边界、你选择的中位数的值，还有分支逻辑都打印输出一下，出现死循环的原因就一目了然了；如果能确定要找的数就在候选区间里，那么退出循环的时候，区间最后收缩成为 1 个数后，直接把这个数返回即可；如果你要找的数有可能不在候选区间里，区间最后收缩成为 1 个数后，还要单独判断一下这个数是否符合题意。 最后给出两个模板，看的时候看注释，不必也无需记忆说明：写的时候，一般是先默认将中位数写成左中位数，再根据分支的情况，看看是否有必要调整成右中位数，即是不是要在 (right - left) 这个括号里面加 1 。
虽说是两个模板，区别在于选中位数，中位数根据分支逻辑来选，原则是区间要收缩，且不出现死循环，退出循环的时候，视情况，有可能需要对最后剩下的数单独做判断。
哈哈哈哈哈
这里是引用
总结的灵感和内容参考链接： 作者：liweiwei1419 链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 来源：力扣（LeetCode）
