王老师_区赛复习6_二分查找

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
//二分查找===折半查找
//比如我们现在有一个数组  长度是1e5  10w
//我们现在想在这个数组里面查找某个数字有没有出现过 ，比如我们要找数字x
//假设要询问10w次，那就会超时
//所以我们需要一个算法，帮助我们快速的查找某个数字有没有在数组里面出现过
//二分查找这个算法，可以帮助我们解决这个问题
//二分查找的特点：思想非常非常好理解，但是代码的细节多一些，要求同学听课认真+思考认真
//现在介绍二分查找的代码逻辑：我们用双指针能够选取一段范围，我们会在这段范围里面寻找我们的目标值
//每一次会把当前这段范围的中间值 和 目标值做比较 大于 等于 小于 直到找到答案 或者l>r
//二分查找是非常非常快 二分查找的前提条件：数组要有序，从小到大
//这个函数是在a数组里面查找数字x有没有出现过，如果数字x出现过 函数返回1 
//如果数字x没有出现过  函数返回0
int bs(int x){//binary_search
    int l=1,r=n;//细节1：左右指针的初始值
    //left  right
    while(l<=r){//细节2：while循环里面的条件100000% 是 l<=r
        int mid=(l+r)/2;//mid是中间
        if(a[mid]==x) return 1;
        if(a[mid]>x)  r=mid-1;//细节3：r=mid   l=mid 一定不可以
        if(a[mid]<x)  l=mid+1;
    }
    return 0;
}
6--> 1 2 2 2 2 2 
//查找数字x  第一次出现的位置
int bs2(int x){//binary_search
    int l=1,r=n,ans=-1;//ans帮助我们记录数字x第一次出现的位置
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x) ans=mid,r=mid-1;
        if(a[mid]>x)  r=mid-1;
        if(a[mid]<x)  l=mid+1;
    }
    return ans;
}
//查找数字x  最后一次出现的位置
int bs3(int x){//binary_search
    int l=1,r=n,ans=-1;//ans帮助我们记录数字x第一次出现的位置
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x) ans=mid,l=mid+1;
        if(a[mid]>x)  r=mid-1;
        if(a[mid]<x)  l=mid+1;
    }
    return ans;
}
//结合bs2和bs3  可以帮助我们快速的计算出来 数字x出现过多少次
//6---> 1 2 3 4 5 6
//在a数组中查找  大于x第一个位置
int  bs4(int x){
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>x) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
//我们使用bs4 可以帮助我们快速的计算 在a数组当中 大于x的数据有几个
//在a数组中查找  大于等于x第一个位置
int  bs5(int x){
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>=x) ans=mid,r=mid-1;
        else l=m+1;
    }
    return ans;
}
//8--->1 2 3 3 4 5 5 6
//在a数组当中 查找小于x的最后一个位置
int  bs6(int x){
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
//在a数组当中 查找小于等于x的最后一个位置
int  bs7(int x){
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<=x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
//结合bs5 和bs7  有组合技 可以帮助我们快速查询 数组中有几个数据的范围在 [x,y]  
//然后如果某个函数返回-1  说明不存数据在这个范围内----->0
int n,a[N];
int main(){




    return 0;
}