利用循环不变式写出正确的二分查找及其衍生算法

约定不等于承诺〃 2022-05-31 04:17 159阅读 0赞

**利用循环不变式写出正确的二分查找及其衍生算法**

# 一.你能准确写出二分查找吗？ #

先看看定义

> 二分查找的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找成功；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

思路很简单以至于大多数人都能讲出来，但是有多少人能一次写出bug-free的代码？《编程之美》第2.16节的最长递增子序列算法，如果想实现O(n2)到O(nlogn)的时间复杂度下降，必须借助于二分算法的变形。其实很多算法都是这样，如果出现了在有序序列中元素的查找，使用二分查找总能提升原先使用线性查找的算法的性能。

很多人觉得二分算法简单，但随手一写会发现诸如死循环，边界条件无法确定的问题，提供充足的时间，仅有约10%的专业程序员能够完成一个正确的二分查找,看来，二分查找并不是我们想象的那么简单。网络上的资料大多对边界值的确定避而不谈，即使进行讲解，思路也有些凌乱并且不适合我这种初学者，在参考多篇文章之后，我对二分算法有了一个新的认识。

————==写出这篇博文献给和我一样对二分查找的思路毫无头绪但又不甘于死记硬背的人们==。

# 二.利用循环不变式来证明边界取值的正确性 #

note:   
1. 本文中，文字说明部分的’=’究竟是赋值还是逻辑判断请根据上下文推断。   
2. 算法推导过程中的mid的计算采用(low+high)/2的方式，因为只是推导，所以无需考虑溢出的问题，但是代码中全部采用low+(high-low)/2,推导过程中可认为两者值相等。   
3. 在理论推导每次数组减少的长度时，mid是不能代换成left + (right - left)/2的。这种形式代表了非整型的运算，没有舍去小数部分，而在实际的运行过程中mid是会舍去小数部分的。

循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法，它是一个需要保证正确断言。对于循环不变式，必须证明它的三个性质：

1.  初始化：它在循环的第一轮迭代开始之前，应该是正确的。
2.  保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。
3.  终止：循环能够终止，并且可以得到期望的结果。

**例1:找出数组中值为v的元素，不存在时返回-1**

初始化:初始区间为\[0,n-1\]，low初始值为0，high初始值为n-1,若v存在于数组中，则其必然存在于区间\[low,high中\]，正确。

保持:

1.  若Array\[mid\]< v,则v应该存在于\[mid+1,high\]区间内，舍弃区间\[low,mid\],数组减小长度为(mid-low+1),则数组每次至少减少1个单位,并且low应该指向mid+1的位置;
2.  若Array\[mid\]==v,则说明找到，返回mid;
3.  若Array\[mid\]>v,则v应该存在于\[low,mid-1\]区间内，舍弃区间\[mid,high\],数组减小长度为(high-mid+1),则数组每次至少减少1个单位,并且high指针应该指向mid-1位置;

终止:

根据上面的讨论，我们明确了每个if判断之后high，low指针的移动情况，但是我们还需要确定循环条件，我们看到，无论是情况1还是情况3，数组每次至少减少1个单位，考虑当low==high时，可以推出low或high==mid，但是我们的数组减小长度要么为(mid-low+1)，要么为(high-mid+1)，不管什么情况总是保证每次减少1，所以不会出现死循环的情况。

根据上面的分析,我们确定循环条件为:low<=high

代码如下:

class Solution {
    public:
        int binSearch(vector<int> &nums,int target) {
            if(nums.empty())
                return -1;
            int low=0,high=n-1,mid=0;
            while(low<=high){
                mid=low+(high-low)/2;
                if(nums[mid]<target)
                    low=mid+1;
                else if(nums[mid]>target)
                    high=mid-1;
                else
                    return mid;
            }
            return -1;
        }
    };

例2:   
**二分查找返回key(可能有重复)第一次出现的下标x，如果不存在返回-1**

初始化:初始区间为\[0,n-1\]，low初始值为0，high初始值为n-1,若v存在于数组中，则其必然存在于区间\[low,high\]，正确。

保持:   
1. 若Array\[mid\]

class Solution {
    public:
        vector<int> searchLow_bound(vector<int>& nums, int target) {
            vector<int> res(2,-1);
            if(nums.empty())
                return res;
            int low=0,size=nums.size(),high=nums.size()-1,mid=0;
            while(low<high){
                mid=low+(high-low)/2;
                if(nums[mid]>target)
                    high=mid-1;
                else if(nums[mid]==target)
                    high=mid;
                else
                    low=mid+1;
            }
            if(nums[low]==target)
                res[0]=low;
        }
    };

**例3.二分查找返回key(可能有重复)最后一次出现的下标x，如果不存在返回-1**

初始化:

初始区间为\[0,n-1\]，low初始值为0，high初始值为n-1,若v存在于数组中，则其必然存在于区间\[low,high\]，正确。

保持:

若Array\[mid\]< v,则v存在于区间\[mid+1,high\],舍弃区间\[low,mid\],区间减少的长度为(mid-low+1),至少为1，同时令low指向mid+1。

若Array\[mid\]==v,则v存在于区间\[mid,high\]，舍弃区间\[low,mid-1\],区间减小长度为(mid-low),同时令low指向mid,根据前面的分析，我们知道这种情况下如果low==high就会出现死循环，同时，如果high==low+1也会导致死循环，因为mid=(low+high)/2。

若Array\[mid\]>v,则v存在于区间\[low,mid-1\],舍弃区间\[mid,high\],区间减小长度为(high-mid+1),至少为1，同时令high指向mid-1的位置。

终止:   
根据上面的讨论，我们知道low必须小于high，且low+1也要小于high。

故循环条件为low+1< high

另外由于是寻找最后一次出现的下标，所以循环结束后还需要检查Array\[low+1\]是否等于target，不相等则检查Array\[low\],若还不相等则查找失败。

代码如下:

class Solution {
    public:
        vector<int> searchLast(vector<int>& nums, int target) {
            vector<int> res(2,-1);
            if(nums.empty())
                return res;
            int low=0,size=nums.size(),high=nums.size()-1,mid=0;
            while(low+1<high){
                mid=low+(high-low)/2;
                if(nums[mid]<target)
                    low=mid+1;
                else if(nums[mid]==target)
                    low=mid;
                else
                    high=mid-1;
            }
            if(nums[low+1]==target&&size>1)
                res[1]=low+1;
            else if(nums[low]==target)
                res[1]=low;
            else
                res[1]=-1;
            return res;
        }
    };

# 三.总结：如何写出正确的二分查找代码？ #

结合以上各个算法，可以找出根据需要写二分查找的规律和具体步骤，比死记硬背要强不少，万变不离其宗嘛：

(1)大体框架必然是二分，那么循环的key与array\[mid\]的比较必不可少，这是基本框架;

(2)循环的条件可以先写一个粗略的，比如原始的while(left<=right)就行，这个循环条件在后面可能需要修改；

(3)确定每次二分的过程，要保证所求的元素必然不在被排除的元素中，换句话说，所求的元素要么在保留的其余元素中，要么可能从一开始就不存在于原始的元素中；

(4)检查每次排除是否会导致保留的候选元素个数的减少？如果没有，分析这个边界条件，如果它能导致循环的结束，那么没有问题；否则，就会陷入死循环。为了避免死循环，需要修改循环条件，使这些情况能够终结。新的循环条件可能有多种选择：while(left< right)、while(left< right-1)等等，这些循环条件的变种同时意味着循环终止时候选数组的形态。

(5)结合新的循环条件，分析终止时的候选元素的形态，并对分析要查找的下标是否它们之中、同时是如何表示的。

对于(3)，有一些二分算法实现不是这样的，它会使left或right在最后一次循环时越界，相应的left或right是查找的目标的最终候选，这一点在理解时需要注意。当然，不利用这个思路也可以写出能完成功能的二分查找，而且易于理解。

应用：

1.查找排序数组中某个数出现的次数。

解法：二分查找确定第一次和最后一次出现的下标，差值+1就是出现次数，时间复杂度O(logn).

参考网址:http://blog.csdn.net/kelvinmao/article/details/52130470