二分搜索技术

例如，给定n个元素序列，这些元素是有序的（假定为升序），从序列中查找元素x。

用一维数组S[]存储该有序序列，设变量low和high表示查找范围的下界和上界，middle表示查找范围的中间位置，x为特定的查找元素。

1．算法步骤

（1）初始化。令low=0，即指向有序数组S[]的第一个元素；high=n−1，即指向有序数组S[]的最后一个元素。

（2）判定low≤high是否成立，如果成立，转向第3步，否则，算法结束。

（3）middle=(low+high)/2，即指向查找范围的中间元素。如果数量较大，为避免low+high溢出，可以采用middle=low+(high-low)/2。

（4）判断x与S[middle]的关系。如果x=S[middle]，则搜索成功，算法结束；如果x>S[middle]，则令low=middle+1；否则令high=middle−1，转向第2步。

2．完美图解

例如，在有序序列（5，8，15，17，25，30，34，39，45，52，60）中查找元素17。

（1）数据结构。用一维数组S[]存储该有序序列，x=17。

（2）初始化。low=0，high=10，计算middle=(low+high)/2=5。

（3）将x与S[middle]比较。x=17 < S[middle]=30，在序列的前半部分查找，令high=middle−1，搜索的范围缩小到子问题S[0..middle−1]。

（4）计算middle=(low+high)/2=2。

（5）将x与S[middle]比较。x=17 > S[middle]=15，在序列的后半部分查找，令low=middle+1，搜索的范围缩小到子问题S[middle+1..high]。

（6）计算middle=(low+high)/2=3。

（7）将x与S[middle]比较。x=S[middle]=17，查找成功，算法结束。

3．算法实现

用BinarySearch（int n，int s[]，int x）函数实现折半查找算法，其中n为元素个数，s[]为有序数组，x为待查找元素。low指向数组的第一个元素，high指向数组的最后一个元素。如果low≤high，middle=(low+high)/2，即指向查找范围的中间元素。如果x=S[middle]，搜索成功，算法结束；如果x>S[middle]，则令low=middle+1，去后半部分搜索；否则令high=middle−1，去前半部分搜索。

（1）非递归算法

​​​​​​​int BinarySearch(int s[],int n,int x){//二分查找非递归算法

   int low=0,high=n-1;  //low指向数组的第一个元素，high指向数组的最后一个元素

   while(low<=high){

       int middle=(low+high)/2;  //middle为查找范围的中间值

       if(x==s[middle])  //x等于查找范围的中间值，算法结束

          return middle;

       else if(x>s[middle]) //x大于查找范围的中间元素，则从左半部分查找

              low=middle+1;

            else            //x小于查找范围的中间元素，则从右半部分查找

              high=middle-1;

    }

    return -1;

}

（2）递归算法

递归有自调用问题，增加两个参数 low 和 high来标记搜索范围的开始和结束。

int recursionBS(int s[],int x,int low,int high){ //二分查找递归算法

    //low指向搜索区间的第一个元素，high指向搜索区间的最后一个元素

    if(low>high)              //递归结束条件

        return -1;

    int middle=(low+high)/2; //计算middle值(查找范围的中间值)

    if(x==s[middle])        //x等于s[middle]，查找成功，算法结束

        return middle;

    else if(x<s[middle]) //x小于s[middle]，则从前半部分查找

            return recursionBS(s,x,low,middle-1);

        else            //x大于s[middle]，则从后半部分查找

            return recursionBS(s,x,middle+1,high);

}

4．算法分析：

（1）时间复杂度

二分查找算法，时间复杂度怎么计算呢？如果用T(n)来表示n个有序元素的二分查找算法的时间复杂度，那么：

• 当n=1时，需要一次比较，T(n)=O(1)。
• 当n>1时，待查找元素和中间位置元素比较，需要O(1)时间，如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为T(n/2)。

二分查找的非递归算法和递归算法查找的方法是一样的，时间复杂度相同，均为O(logn)。

（2）空间复杂度

二分查找的非递归算法中，变量占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为O(1)。

二分查找的递归算法，除了使用一些变量外，递归调用还需要使用栈来实现。在递归算法中，每一次递归调用都需要一个栈空间存储，那么我们只需要看看有多少次调用。假设原问题的规模为n，那么第一次递归就分为两个规模为n/2的子问题，这两个子问题并不是每个都执行，只会执行其中之一。因为和中间值比较后，要么去前半部分查找，要么去后半部分查找；然后再把规模为n/2的子问题继续划分为两个规模为n/4的子问题，选择其一；继续分治下去，最坏的情况会分治到只剩下一个数值，那么算法执行的节点数就是从树根到叶子所经过的节点，每一层执行一个，直到最后一层，如图所示。

递归调用最终的规模为1，即n/2x=1，则x=logn。假设阴影部分是搜索经过的路径，一共经过了logn个节点，也就是说递归调用了logn次。递归算法使用的栈空间为递归树的深度，因此二分查找递归算法的空间复杂度为O(logn)。

二分搜索需要注意的几个问题：

（1）必须满足有序性。

（2）搜索范围。初始时，需要指定搜索范围，如果不知道具体范围，正数可以采用范围[0,inf]，有可能为负数可以采用范围[-inf,inf]，inf为无穷大，通常设定为0x3f3f3f3f。

（3）二分搜索。一般情况下，mid=(l+r)/2或mid=(l+r)>>1。如果l和r特别大，为避免l+r溢出，可以采用mid=l+(r-l)/2。判断二分搜索结束的条件，以及当判断mid可行时到前半部分搜索，还是到后半部分搜索，需要具体问题具体分析。

（4）答案是什么。特别小心搜索范围减少时，是否丢失在mid点上的答案。

二分搜索分为整数上的二分搜索和实数上的二分搜索，大致模板如下。

1. 整数上的二分搜索

整数上的二分搜索，因为缩小搜索范围时，有可能r=mid-1或l=mid+1，因此可以用ans记录可行解。是否需要减1或加1，要根据具体问题分析。

l=a; r=b; //初始搜索范围

while(l<=r){

   int mid=(l+r)/2;

   if(judge(mid)){

      ans=mid; //记录可行解

      r=mid-1;

   }

   else

     l=mid+1;

}

return ans;

2. 实数上的二分搜索

实数上的二分搜索不可以直接比较大小，可以采用r-l>eps作为循环条件，eps为一个较小的数，如1e-7等。为避免丢失可能解，缩小范围时r=mid或l=mid，循环结束时返回最后一个可行解。

l=a; r=b; //初始搜索范围

while(r-l>eps){//判断差值

    double mid=(l+r)/2;

    if(judge(mid))

        l=mid;  //l记录了可行解，循环结束后返回答案l

    else

        r=mid;

}

return l;

还可以运行固定的次数，如运行100次，可达10-30精度，一般

情况都可以解决问题。

l=a; r=b;

for(int i=0;i<100;i++){//运行100次

    double mid=(l+r)/2;

    if(judge(mid))

        l=mid;

    else

        r=mid;

}

return l;

二分搜索刷题下次分解。