精确二分查找/上下取整

Author Avatar
LittleBlack 7月 03, 2019
  • 在其它设备中阅读本文章

精确的二分查找

思路

  • 第一个就是返回true 和 false 的精确查找,稍微改动即可实现查找
  • C++里面有lower_bound(),upper_bound() 实现上取整下取整的,本文的第二个、第三个函数就是等价于这两个函数的

具体代码

先提供main和头文件等(下面的二分和这里的main是些一个文件里的)

#include <iostream>
using namespace std;

const int MAXN=1000;    //设好一个最大长度,可以更改 
int n,m,a[MAXN];    //n为长度,m为要查找的数 
//下面放函数区



//上面放函数区
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];    //输出升序数列 
    bool flag=bs(1,n,m);    //1固定为开始,n为长度,m为要查找的数 
    if(flag) puts("true");    //将flag==true省略成flag 
    else puts("false");    //puts大概只能输出字符串 
    return 0;
}

精确查找(判断有没有)

bool bs(int low,int high,int x) {    //精确的二分查找(判断有没有) 
    int l=low,r=high;    //不直接更改参数 
    while(l<=r) {
        int mid=l+(r-l)/2; //完全等价(l+r)/2
        if(x==a[mid]) {    //就是找到了 
            return true;
        } else if(x>a[mid]) {
            l=mid+1;    //更改左箭头 
        } else {
            r=mid-1;    //更改右箭头 
        }
    }
    return false;    //没有找到 
}

要注意上边界和下边界一般是组合在一起使用的

下边界

int bs_low(int low,int high,int x) {    //查找下边界(这个数最左边出现的地方)
    int l=low,r=high;
    while(l<r) {//注意不是l=r 
        int mid=(l+r)/2; //下边界的mid一样 
        if(x<=a[mid]) {
            r=mid;
        } else if(x>a[mid]) {
            l=mid+1;
        }
    }
    return r;    //它一定会返回r
}

上边界

int bs_high(int low,int high,int x) {    //查找上边界(这个数最右边出现的地方) 
    int l=low,r=high;
    while(l<r) {
        int mid=(l+r+1)/2;    //+1 是上取整
        if(x>=a[mid]) {
                l=mid;//因为是上边界取整,所以这边也有变化
        } else if(x<a[mid]) {
            r=mid-1;//变化
        }
    }
    return l;
}

总结

  1. 一定要理解,注意+1-1 、边界情况、会不会死在一起
  2. 实在不理解就把它给背下来,这几个东西很重要
  3. 如果是做程序填空题,注意有时填的语句可以不止一个,不要死
  4. 样例代码下载:https://pan.baidu.com/s/12yJQyn8SNd-ecmt-UKIsOg