写出正确的二分搜索知易行难，原理好像都懂，但是实际上手就出各种错误，例如如何确定循环终止条件、区间搜小判断条件等。这里就手把手教你写出正确的二分检索！

二分法共有下面7种变式。

①是否存在数字t ——返回下标或者-1

②找到大于t的第一个数 ——返回下标或者-1

③找到大于等于t的第一个数 ——返回下标或者-1

④找到小于t的最后一个数 ——返回下标或者-1

⑤找到小于等于t的最后一个数 ——返回下标或者-1

⑥是否存在数字t，返回第一个t ——返回下标或者-1

⑦是否存在数字t，返回最后一个t ——返回下标或者-1

首先说一点个人思考，情况1（查找target位置）完全就是抖了个机灵，用情况1来当作二分查找的基本情况是非常非常错误的，从情况1完全不能推导出其他情况下二分查找该如何写。看了很多篇博客，没有一篇兼顾了正确性证明和归纳性。下面是我阅读过《Elements of programming》了解二分法原理后，自己扩展出的二分法各种变式。每一种情况都有正确性证明，且条件归纳统一，归纳性强，很好理解。

一、二分法的适用条件——P划分区间

想要用好二分法，就要先搞清楚什么是二分法及其适用条件，即什么样的问题可用二分法解决，如何解决。答案是二分法的每一种变式，都是在P划分区间上查找划分点。下面介绍P划分区间和划分点的概念。

P划分区间：给定一个元素为s_i的闭区间S和一个对s的判断条件P（即P(s)返回true或者false），如果S中存在某个元素s_x使得区间上在s_x之前的元素（不包括s_x）都不满足P，而s_x及其之后的元素（包括s_x）都满足P，那么就称区间S是P划分的，且s_x是划分点，下面简写为划分点x。

直白形象的说，S是一个区间，x∈S，x之前的元素（不包括x）都不满足P，而x及其之后的元素（包括x）都满足P。就像这样

此例中，s4即为划分点。

划分点能带给我们什么信息呢？

1）对于S中任意一个元素s_i，若s_i满足P，那么s_i后面的元素都满足条件P。

2）对于S中任意一个元素s_i，若s_i不满足P，那么s_i前面的元素都不满足条件P。

二、情况2、3，第一个满足条件的元素

大于或大于等于target，就是一个条件P。二分查找中，区间S中元素是升序的，显然S满足P划分。所以我们的任务就是找到第一个满足P的元素，也就是划分点。先给出代码

int findPartition(vector<int> nums,bool (*P)(int)) {
    if(P(nums[nums.size() - 1]) == false) return -1; //there no partition point             
    int left = 0,right = nums.size() - 1,mid;                                     
    while(left < right){                           
        mid = left + ((right - left) >> 1);                                 
        if(P(nums[mid])){                           
            right = mid;                           
        }else{                                     
            left = mid + 1;                        
        }                                          
    }                                              
    return left;                                   
}

我们从以下三方面证明算法的正确性：

1）若划分点不存在，函数返回 -1

2）若划分点存在，算法必然终止。

3）若划分点存在，算法终止时，left所指元素即为划分点。

证明：

1）如果不存在划分点，那说明区间中的元素都不满足条件P，此时只需要用区间最后一个元素对P进行检查即可。算法第2行代码如果最后一个元素都不满足P，那么区间中所有元素都不满足P，也就没有划分点，返回-1，算法结束。

2）：mid = (left + right) / 2，即left和right的中位数向下取整，可见mid >= left。又因为while循环条件为left不等于right，故而循环体中mid < right。所以每次迭代，区间长度至少减1。当区间长度为1时，算法终止，此时left 等于right。

3）：观察while循环体中内容，如果第6行判断mid位置元素满足断言P，那么划分点x要么位置是mid，要么在mid前面，但肯定不会在mid后面了，故而我们把right指向mid（第7行），排除掉mid后面的元素（不包括mid）。如果第6行判断条件为false，那么说明mid位置上的元素不满足P，且mid之前的元素都不满足P，故而我们把left指向mid + 1（第9行），排除掉mid及其前面的元素（包括mid）。熟悉不变式的同学肯定明白了，每次迭代，都满足划分点一定在闭区间[left，right]，且这个区间一直在缩小，当区间长度为1，left等于right，此时区间内的唯一元素就必然是划分点。

三、情况4、5，最后一个满足条件的元素

小于或小于等于target，就是一个条件P，我们要找到满足条件P的最后一个元素。此时有两种方法，第一种是找满足！P的第一个元素，然后返回（其下标-1）。第二种是灵活修改一下划分区间和划分点的定义。

此时S3是划分点，即最后一个满足条件P的元素，代码如下

int findPartition(vector<int> nums,bool (*P)(int)) {
    if(P(nums[0]) == false) return -1; //there no partition point             
    int left = 0,right = nums.size() - 1,mid;                                     
    while(left < right){                           
        mid = left + ((right - left + 1) >> 1); //attention,up[(left + right) / 2]                              
        if(P(nums[mid])){                           
            left = mid;                          
        }else{                                     
            right = mid - 1;                        
        }                                          
    }                                              
    return left;                                   
}

正确性证明同理情况2、3，有两点注意

1）代码第2行，利用区间第一个元素来判断是否有划分点的存在。如果第一个元素都不满足P，那么区间中所有元素都不满足P，返回-1。

2）代码第5行，计算中位数时候，要取left和right的向上取整，这样就有left < mid，mid <=right，才能保证区间长度一直在减小，算法必然终止。

四、情况6、7，在情况2、3、4、5基础上加入等于条件

要找是否存在某数，返回其第一个或是最后一个的位置，这可以当作之前情况的扩展，感谢这篇博客给我的思路。以下两点即可解决此种情况

查找第一个t，即查找第一个大于等于t的元素，还要专门考虑此数存不存在。
查找最后一个t，即查找最后一个小于等于t的元素，还要专门考虑此数存不存在。

代码在之前的基础上，return时增加判断条件nums[left] == target即可。

return nums[left] == target ? left : -1;

OK，这就是我归纳的二分搜索写法，欢迎交流。

原文链接：https://blog.csdn.net/qwe1173529071/article/details/104432374