二分查找与二分答案(2)

溢出风险

 我们首先回顾一下上一次二分算法的代码

#include<iostream>
using namespace std;
int n,x,a[1000000];
int binary_search(int a[],int n,int x)
{
    int l = 0;
    int r = n - 1;
    int ans = -1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if(a[m] == x)
        {
            ans = m;
            break;
        }
        if(a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return ans;
} 
int main()
{
    cin >> n >> x;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    int ans = binary_search(a,n,x);
    cout << ans;
    return 0;
}

 之所以重新把代码拿出来,肯定是因为有不妥之处,我们看一下第11行m=(l+r)/2  假如l=1999999998,r=1999999999,虽然l和r都没有超出int的范围,但是计算m时,l+r就超过int范围了,导致m计算错误,整个算法挂掉  解决办法很简单,改成m=l+(r-l)/2,这样就不会有溢出的风险了

其他问题

 我们解决了最简单的二分查找问题:a数组单调递增,并且其中没有重复的数值。我们遇到的实际问题可能就没有这么简单,可能会有重复的数值。比如a数组里有3个5。这时我们查找5就有一个问题:到底返回哪一个5的下标?  此外,在之前的简单版本中,如果查找的x不在数组中,我们就返回-1。但是实际的问题中,即便x不在数组中,我们可能需要知道与x大小接近的数值在数组中处于什么位置。不能只返回一个-1了事。  为了解决这些问题,C++STL提供了两个特别好用的函数:lower_bound()和upper_bound()

lower_bound()

 假设有一个a数组,数组长度是n,lower_bound(a,a+n,x)返回数组a[0]~a[n-1],大于等于x的数中,最小的数的指针。由于指针可以通过加减算偏移量,所以我们再减去a(数组名会被隐式转换成指针),就得到了相应的下标。下面给个例子,假设我们在a数组中找3这个数。

 左边是a数组,当然这个a数组必须递增的,不然lower_bound()会出错。其中标红的是大于等于3的数。右边是lower_bound()的返回值减去a,是标红这些数里最小的一个的下标。注意最后一个例子,如果a数组中一个大于等于3的都没有,会返回数组长度n。

upper_bound()

 同样假设a是一个数组,n是数组长度,upper_bound(a, a+n, x)返回数组a[0]~a[n-1]中,大于x的数中,最小的数的指针。<font color = red>注意lower_bound是“大于等于”,upper_bound是“大于”。</font>

 标红的部分是a数组中大于3的数。upper_bound的返回值减去a是这些数里最小的一个的下标。  其实对于lower_bound和upper_bound还有一个等价的解释。就是假设我要在a数组中插入x,然后还保持递增,那么lower_bound返回的是x最小的可以插入的数组位置,upper_bound返回的是x最大的可以插入的数组位置。

 可以参考上面的图,当然lower_bound和upper_bound并不是真的返回2和5,返回的是指针,减去a之后才是2和5  我们通过一个程序看一下lower_bound和upper_bound的用法

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[10] = {1,2,2,3,3,3,4,4,4,4};
    int n = 10;
    for(int i = 0;i <= 5;i++)
    {
        int *lower = lower_bound(a,a + n,i);//循环查找最小大于等于i的指针
        int *upper = upper_bound(a,a + n,i);//循环查找最小大于i的指针 
        cout << lower - a << " " << upper - a << endl;
    }
    return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10 
*/

 另外lower_bound和upper_bound的前两个参数是其实是待查范围的首尾指针(左闭右开区间,不包括尾指针),所以也可以写别的参数。比如下面的程序就是从a[1]开始查找:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[10] = {1,2,2,3,3,3,4,4,4,4};
    int n = 10;
    for(int i = 0;i <= 5;i++)
    {
        int *lower = lower_bound(a + 1,a + n,i);//循环查找最小大于等于i的指针
        int *upper = upper_bound(a + 1,a + n,i);//循环查找最小大于i的指针 
        cout << lower - a << " " << upper - a << endl;
    }
    return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10 
*/

 lower_bound和upper_bound除了能用在数组上,还可以用在vector上。我们知道vector就相当于一个可以长度可变的数组。当用于vector上时,需要注意前两个参数必须是vector的迭代器,同时函数的返回值也是迭代器:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[10] = {1,2,2,3,3,3,4,4,4,4};
    vector<int> b(a,a + 10);
    int n = 10;
    for(int i = 0;i <= 5;i++)
    {
        vector<int>::iterator lower = lower_bound(b.begin(),b.end(),i);//循环查找最小大于等于i的指针
        vector<int>::iterator upper = upper_bound(b.begin(),b.end(),i);//循环查找最小大于i的指针 
        cout << lower - b.begin() << " " << upper - b.begin() << endl;
    }
    return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10 
*/
自定义lower_bound()和upper_bound()函数
  1. my_lower_bound()函数

 首先函数my_lower_bound(int a[],int n,int x)的参数分别是数组a,数组a的长度,带查找的元素x,而这个函数的实现,其实稍微改一下我们之前的二分查找代码即可

#include<iostream>
using namespace std;
int n,x,a[1000000];
int my_lower_bound(int a[],int n,int x)
{
    int l = 0;
    int r = n - 1;
    int ans = n;
    while(l <= r)
    {
        int m = l + (r - l) / 2;
        if(a[m] >= x)
        {
            ans = m;
            r = m - 1;
        }
        else
            r = m + 1;
    }
    return ans;
} 
int main()
{
    cin >> n >> x;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    int lower = my_lower_bound(a,n,x);
    cout << lower;
    return 0;
}

 关键代码从第12行开始。如果中间的这个数a[m]是大于等于x的。记得我们要找的是”大于等于x的数中最小的数的下标“。现在我们发现了一个大于等于x的数a[m],当前这个下标m是我们已知最小的,所以就在第13行把m的值赋值给答案ans。然后因为我们已经知道a[m]是一个“大于等于x的数”,所以a[m+1], a[m+2]…a[r]都不用再考虑了。只需要在a[l]~a[m-1]中查找是不是还有大于等于x的数”,于是第15行我们令r = m – 1。  如果a[m]<x,那a[l], a[l+1], … a[m]一定都小于x,都不满足”大于等于x”这个条件。所以我们只需要在a[m+1], a[m+2], … a[r]中再查找x。于是第18行我们令l = m + 1  my_upper_bound()的函数我就不写了,upper_bound是找“大于x的数中,最小数的下标”,而lower_bound是找“大于等于x的数中,最小数的下标”,所以对于my_upper_bound函数,我们只要把上面代码中第12行的“a[m]>=x”改成“a[m]>x”即可

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

python3--迭代器,生成器

现在是从结果分析原因,能被for循环的就是"可迭代的",但是如果按常规想,for怎么知道谁是可迭代的呢?

891
来自专栏Deep learning进阶路

C++随记(八)---存储持续性、作用域和链接性

版权声明:本篇文章是阅读《C++primer plus (第6版)中文版》第9章之后所作的笔记。部分文字和图表摘自于这本书。 C++随记(八)---存储持续性、...

1790
来自专栏前端进阶之路

JS学习系列 06 - 变量对象

上一节我们讨论了执行上下文,那么在上下文中到底有什么内容,为什么它会和作用域链扯上关系,JS 解释器又是怎么找到我们声明的函数和变量,看完这一节,相信大家就不会...

492
来自专栏老九学堂

稳准狠!最全讲解!初学者必看的C语言字符串知识

字符数组和普通数组一样,也是通过下标引用各个元素。 【示例】输出字符数组中的元素。

701
来自专栏老司机的技术博客

人人都能学会的python编程教程12:函数的参数

Python的函数定义非常简单,也非常灵活。除了正常定义的必选参数外,还可以使用默认参数、可变参数和关键字参数,使得函数定义出来的接口,不但能处理复杂的参数,还...

4707
来自专栏玄魂工作室

Python学习:类和实例

-----------------------------------------------------

883
来自专栏程序员互动联盟

【专业技术第二讲】c语言中const的使用

遇到有人为const的使用: ? 这里对const的使用做一个大致的总结。 C语言的const关键字与指针搭配使用,const是C语言中保留的一个关键字,它用来...

3426
来自专栏移动端开发

Swift2.0 函数学习笔记

最近又有点忙,忙着找工作,忙着适应这个新环境。现在好了,上班两周周了,也适应过来了,又有时间安安静静的就行我们前面的学习了。今天这篇笔记,记录的就是函数的使用。...

1826
来自专栏老司机的技术博客

宝宝都能学会的python编程教程12:函数的参数

Python的函数定义非常简单,也非常灵活。除了正常定义的必选参数外,还可以使用默认参数、可变参数和关键字参数,使得函数定义出来的接口,不但能处理复杂的参数,还...

3366
来自专栏天天

数据储存

702

扫码关注云+社区