二分查找 | Eviden🥝

二分查找,请注意边界,看懂题意要查找的到底是哪种满足答案的解!

Q1:什么是lower_bound/upper_bound?

这两个函数是STL中用于二分查找的两个函数，用法：假定我们有一个有序的数组a，并将数x作为二分查找的目标，那么：

1 2	lower_bound(a,a+n,x)-a //下标从0开始 lower_bound(a+1,a+n+1,x)-a //下标从1开始

这样就能取得最小的a数组下标i,满足a_i>=x

1 2	upper_bound(a,a+n,x)-a //下标从0开始 upper_bound(a+1,a+n+1,x)-a //下标从1开始

它们就能取得最小的a数组的下标i，满足a_i>x

手动实现查找

#include<iostream>

using namespace std;

/*
---------如何理解这两种搜索的区别呢,主要是while条件的不同
---------如果是搜具体的某个数(一般是直接搜到答案),也就是直接搜二分时mid的值,直接返回mid
---------但是如果不是搜具体的某个数,而是搜索一段区间,即返回的不是mid而是left或right这种边界
---------那么此时返回的状态其实是最后一次搜索结果的前一个(或者几个)状态 

---------如何理解这个left+1<right
-----这里的'1'可以表示left和right之间相差多少时退出循环!
-----除了搜最后一次外可以while退出时写等号,其他时候维护距离不能写=!
-----这里的传参传的是有效数组的后一位,如果刚好传有效数组那么长,搜不到当解是最后一个的情况
-----因此尽量开大一点点数组

*/
bool check1(int index,int tar){
    if(index < tar)return true;
    return false;
}
bool check2(int index,int tar){
    if(index > tar)return true;
    return false;
}
int binasearch_lower(int n[],int size,int tar){
    //0 1 | 3, 3, 3, 5, 7
    //看这个分界线
    int left=0,right=size;
    while (left+1<right)
    {
        /* code */
        int mid = (left+right)/2;
        if(check1(n[mid],tar)){
            left=mid;
        }else right=mid;
    }
    if(n[right]==tar)return right;
    else return -1; 
}

int binasearch_upper(int n[],int size,int tar){
    //1 , 3, 3, 3,| 5, 7
    //看这个分界线
    int left=0,right=size;
    while (left+1<right)
    {
        /* code */
        int mid = (left+right)/2;
        if(check2(n[mid],tar)){
            right=mid;
        }else left=mid;
    }
    if(n[left]==tar)return left;
    else return -1;
    // return 0;
}
bool testsearch(int n[],int size,int tar){
    int l=0,r=size;
    while(l+0<=r){
        int mid = (l+r)/2;
        if(n[mid]==tar)return true;
        else{
            if(n[mid]>tar)r=mid-1;
            else l=mid+1;
        }
    }
    return false;
}

int main(){
    int a[12]={0,1 ,3, 3, 3, 5, 7, 9, 11, 13, 15};
    int b[8]={1,2,3,4,5,6,7,8};
    cout<<binasearch_lower(a,12,9)<<' '<<binasearch_upper(a,12,9)<<endl;
    cout<<testsearch(b,8,4);
}

零点判定定理求根:一元三次方程求根

#include<iostream>

using namespace std ;
double a,b,c,d;
bool check(double l,double r){
    //maybe is 零点存在定理
    //0.01 0.02 0.03 x 0.04 0.05 0.06
    if( (a*l*l*l + b*l*l + c*l + d)*(a*r*r*r+b*r*r+c*r+d)<=0){
        return true;
    }
    else return false;
}
double cal(double l){
    return a*l*l*l + b*l*l + c*l + d;
}

int main(){

    cin>>a>>b>>c>>d;
    double l=-100,r=100;
    int cnt=0;//找到3个解直接退出
    for(int i=-100;i<100;i++){
    l=i;
    r=i+1;
    double r1=cal(l),r2=cal(r);
    if(!r1){
        printf("%.2lf ",l);
        cnt++;
    }
    double mid;
    if(r1*r2<0)
    {   
     while(r-l>=0.001){
        mid = (l+r)/2;
        if(cal(mid)*cal(r)<=0)l=mid;
        else r=mid; 
    }
    printf("%.2lf ",mid);
    cnt++;
    }
    if(cnt==3)break;

    }
}