二分查找的延伸

发布于 2020-02-17  601 次阅读

这篇文章解决若干问题：

如果递增序列A中的元素可能重复，那么如何对给定想查找的元素x：

  • 求出序列中第一个大于等于x的元素的位置；
  • 求出序列中第一个大于x的元素的位置；
  • 求出序列中第一个满足某条件的位置；
  • 求出序列中最后一个小于等于x的元素的位置；
  • 求出序列中最后一个小于x的元素的位置。

第一个大于等于x和第一个大于x的元素的位置

举个栗子：对数组序列{1,3,3,3,6}（下标从0开始）来说，若查询3，则得到L=1、R=4。
如果查询8，则得到L=R=5。
如果序列中没有x，那么L和R也可以理解为假设序列中存在x，则x应当在的位置。

现在，来解决第一个小问吧。

如果已经对二分查找能单独根据脑子里的想的写出代码的时候，lower_bound和upper_bound也能写出来。下面给出代码，读者可以尝试画个数组后按代码中算法推导出来。

其中注意：
对于lower_bound
第一
循环条件为left<right，而不是二分查找的left<=right。在二手查找的问题中，需要元素不存在时返回-1，这样当left>right时[left,right]就不再是闭区间（失去比较的意义），因此可以作为元素不存在的判定规则。
但是如果想要返回第一个大于等于x的元素的位置，就需要判断元素x本身是否存在（就算不存在，返回的也是“若存在应该在的位置”），于是乎当left<right时让循环一直执行即可。
第二
由于left==right时while循环终止，因此最后的返回值既可以是left，也可以是right。
最后
二分的初始区间的原则是应当能覆盖到所有可能返回的结果。
二分下界0可以确定，但是上界是n还是n-1？考虑到想要查询元素x有可能比序列中所有元素都要大，此时应该返回n（若n在数列中存在则它应该在的位置）。因此上界为n。
二分的初始区间为[left,right]=[0,n]。

代码如下:

//left=0 right=n(注意不是n-1)
int lower_bound(int A[],int left,int right,int x){  //对于元素x，就算不存在于A中，也可以返回所需要的值
    int mid;
    while(left<right){  //left==right意味着找到了唯一的位置
        mid=(left+right)/2;
        if(A[mid]>=x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;  //返回查找的位置(当left==right时，循环停止，所以此时left=right)
}
int upper_bound(int A[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(A[mid]>x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;//返回查找的位置(此时left>right，left即为第一个大于x的元素的位置)
}

第一个满足某条件 C 的位置

寻找有序序列中第一个满足某条件 C 的元素的位置

代码如下：

//二分区间为左闭右闭的[left, right]，初值必须能覆盖解的所有可能取值
int solve(int left, int right)
{
    int mid;
    while(left < right)//对于[left,right],两者相同即找到唯一位置
    {
        mid = left + right / 2;
        if (条件成立)        //条件成立，第一个满足条件的元素的位置 <=mid
        {
            right = mid;  //往左子区间[left, mid]找
        }
        else    //条件不成立，第一个满足该条件的位置>mid
        {
            left = mid + 1;  //往右子区间[mid+1, right]找
        }
    }
    return left; //最后返回夹出来的位置
}

举个栗子：

想要求第一个满足大于等于10的元素，则可以这样写。

代码如下：

#include<stdio.h>
//二分区间为左闭右闭的[left, right]，初值必须能覆盖解的所有可能取值
const int n = 10;
int solve(int A[], int left, int right)
{
    int mid;
    while(left < right)//对于[left,right],两者相同即找到唯一位置
    {
        mid = (left + right) / 2;
        if (A[mid] >= 10)        //条件成立，第一个满足条件的元素的位置 <=mid
        {
            right = mid;  //往左子区间[left, mid]找
        }
        else    //条件不成立，第一个满足该条件的位置>mid
        {
            left = mid + 1;  //往右子区间[mid+1, right]找
        }
    }
    return left; //最后返回夹出来的位置
}
int main(){
    int a[n] = {2,5,8,11,13,14,18,20,22,25};
    printf("%d\n",solve(a,0,n));
    return 0;
}

如果寻找最后一个满足“条件C”的元素的位置，则可以先求第一个满足“条件!C”的元素的位置。（比如，最长回文子串就用到了这一点）

先挖个坑，以后回来补

模板拓展（区间左开右闭）

实际上这种左开右闭区间的写法与左闭右闭区间的写法是等价的。
在这种写法下，循环条件变成了left + 1 < right，并且当left+1==right退出循环，使得(left,right]是唯一位置。
由于从左闭变成了左开，因此left的初值要比解的最小值小1（例如对下标为0序列，left的初值为-1，而right的初值不变，还是n），同时，left=mid+1应该改成left=mid（这里想想为什么？挖坑，待解决），并且，返回的值应该是right，而不是left。

//二分区间为左闭右闭的(left, right]，初值必须能覆盖解的所有可能取值
int solve(int left, int right)
{
int mid;
while(left + 1 < right)
{
mid = (left + right) / 2;
if (条件成立)        //条件成立，第一个满足条件的元素的位置 <=mid
{
right = mid;
}
else    //条件不成立，第一个满足该条件的位置>mid 
{
left = mid;
}
}
return right;
}

举个栗子：
同样求第一个大于等于10的元素。
代码如下：

#include<stdio.h>
//二分区间为左开右闭的(left, right]，初值必须能覆盖解的所有可能取值
const int n = 10;
int solve(int A[], int left, int right)
{
int mid;
while(left + 1 < right)//对于[left+1,right],两者相同即找到唯一位置
{
mid = (left + right) / 2;
if (A[mid] >= 10)        //条件成立，第一个满足条件的元素的位置 <=mid
{
right = mid;  //往左子区间[left, mid]找
}
else    //条件不成立，第一个满足该条件的位置>mid
{
left = mid;  //往右子区间[mid, right]找
}
}
return right; //最后返回夹出来的位置
}
int main(){
int a[n] = {2,5,8,11,13,14,18,20,22,25};
printf("%d\n",solve(a,-1,n));
return 0;
}

输出：3
值得注意的是，如果solve函数中返回的是left，则输出2。

最后一个小于等于x和最后一个小于x的元素的位置

既然我们现在已经能求出序列中第一个大于等于x的元素的位置和第一个大于x的元素的位置这种问题了。

那怎么求出最后一个小于等于x的位置和求出最后一个小于x的位置？

只要按照lower_bound和upper_bound的算法自己进行推算，就能出答案了，下面是博主自己根据上面推算的代码。如果有错误，请指正。

代码：

#include <iostream>
using namespace std;
int lower_bound(int A[], int left, int right, int x){
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(A[mid] <= x)
                left = mid + 1;
            else
                right = mid -1;
        }
    return right;
}
int upper_bound(int A[], int left, int right, int x){
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(A[mid] < x)
                left = mid + 1;
            else
                right = mid -1;
        }
    return right;
}
int main(){
    int n, x;
    cin>>n;
    cin>>x;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    cout << lower_bound(a, 0, n-1, x) <<" "<< upper_bound(a, 0, n-1, x);
    return 0;
}

这里提供另外一种参数仅供参考:

int lower_bound(int a[], int n, int x){
        int left = 0 , right = n - 1,  mid;
        ......
}
int upper_bound(int a[], int n, int x){
        int left = 0 , right = n - 1,  mid;
        ......
}
int main(){
    ......
    cout << lower_bound(a, n, x) <<" "<< upper_bound(a, n, x);
    ......
}

参考

3.9-2求解查找最后一个小于等于指定元素的问题

二分算法(详细分类版)

版权所有：可定博客 © WNAG.COM.CN

本文标题：《二分查找的延伸》

本文链接：https://wnag.com.cn/833.html

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~

正因为有要好好实现的梦想，所以今天也要好好加油。