二分查找的延伸

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


这篇文章解决若干问题:

如果递增序列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求解查找最后一个小于等于指定元素的问题

二分算法(详细分类版)

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

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

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


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