目录

 1. 什么是二分查找

 二分查找的功能有多强大？

2. 左闭右闭 左闭右开和左开右闭

3. 处理三种情况的代码：

3.1 左闭右闭代码实现

3.2 左闭右开代码实现

3.3 左开右闭代码实现

 4.区别详解

4.1 mid的偏移

4.2 循环条件的差别及原因

4.3 mid的取值方式及其原因

5. 总结 

6.  二分查找的两段性问题

写在前面：

首先问大家一个问题：你真的完全理解二分查找了吗？

在接触到二分查找的细节之前我也这么认为，但其实二分查找难的并不是它的思想，而是它的细节处理。

如果你对二分查找的边界问题及两段性有很好的理解，那么这篇博客就对你来说是没有用的，但是对于没听说过它的边界问题以及两段性的人来说，这是一篇有价值的博客。

本次本文就二分查找的边界处理及其延伸的两段性为大家带来讲解。

如果你没有了解过二分查找，那么点这里：图解二分查找https://blog.csdn.net/m0_63303316/article/details/122443029?spm=1001.2014.3001.5501

下面为大家举个栗子：

要在有序的1~1000个数字中找一个数字，如果通过遍历的方式来找数字的话，最坏的结果需要找1000次，而通过二分查找，每次都范围都折半，最多只要找10次，时间复杂度由O(n)变为O(logn)，在公司中，这也是经常被使用到的算法。

ps：这里将用一道例题的三种不同解法来像大家解释什么是左闭右闭 左闭右开和左开右闭

704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/binary-search/

 三种取值范围的写法区别在于：

(1)每次折半的时候两端的坐标应该移到mid的位置上还是多偏移一个元素

(2)while判断结束的条件是left nums[mid]) { left = mid;//差别4 } else { ans = mid; break; } } return ans; }  4.区别详解 4.1 left和right的偏移

当我们确定取值范围后，在缩小它的取值范围的过程中要保持一致，如下：

首先：假设我们查找的值为2

(1)若取值范围为左闭右闭，要找的值比mid小，那么right就应该移到mid-1的位置上；要找的值比mid小，那么left就应该移到mid+1的位置上

原因是：由于一开始确定的取值范围为[left,right]，因此在后续查找缩小范围的时候，right也应该保持闭区间的形式，由于此时要找的值为2，mid的值为3，而mid的值由于已经被比较过了才得知mid比要找的值大，因此待搜索的范围缩小为[left,mid-1]。

(2)若取值范围为左闭右开，要找的值比mid小，那么right就应该移动到mid上；要找的值比mid小left就应该移动到mid+1上。

 原因是：由于有一开始确定的范围为[left,right)，后续缩小范围的时候right也要保持开区间。由于mid的值已经被比较过，因此待搜索的范围缩小为[left,mid)。

 如果right=mid-1，也就意味着搜索的范围变为[left,mid-1)了，由于3就落在mid-1的坐标上，如果你要查找的数字为3，那么3是查找不到的。

(3)同(2)理：若取值范围为左开右闭，要找的值比mid小，那么right就应该移动到mid-1上；要找的值比mid小left就应该移动到mid上。

接下来我将就左闭右开的情况为大家举几个例子：

①假设一个数组为{0，1，2，3，4，5，6，7，8，9}，需要索引的值为4

第一次我们的mid值为5，mid指向数字5，如果用right = mid-1处理，那么它的索引范围就变成[0,4)那么数字4就索引不到：

​​​​​​​​​​​​​​

我们发现mid无法索引到存在的4， 因此在左闭右开的情况下用right=mid-1处理是不靠谱的，必须使用right=mid来处理。

同理：在左开右闭的情况写写成left=mid+1同样也是不靠谱的，必须用left=mid来处理

 -----------------------✂---------------------------    

②假设一个数组为{0，1，2，3，4，5，6，7，8，9}，

如果用left=mid处理，有可能找有些值就会死循环。

这里我们假设某种情况下left指向6，right指向7

第一次mid会指向6，如果用left=mid处理，则left还是指向6，从而进入死循环，因此在左闭右开的情况下用left=mid处理时不靠谱的。 

 同理：在左闭右闭的情况下必须用left=mid+1，right=mid-1处理；左开右闭的情况下必须用right=mid-1处理

如果为左闭右闭那么while里面的判断语句是left