c++ binary_search , lower_idx, upper_idx 코드 구현 모음과 차이점 비교.

int n;
int a[500'005];

int binary_search(int target){
    int st=0;
    int en=n-1;
    while(st<=en){
        int mid=(st+en)/2;
        if(a[mid]>target) 
            en=mid-1;
        else if(a[mid]<target)
            st=mid+1;
        else
            return 1;
    }
    return 0;
}
int lower_idx(int target, int len){
    int st=0;
    int en=len;
    while(st<en){
        int mid=(st+en)/2;
        if(a[mid]>=target)
            en=mid;
        else
            st=mid+1;
    }
    return st;// en==mid==st가 되었을때 st 값을 출력하면 lower_idx를 출력하게 된다.
}
int upper_idx(int target,int len){
    int st=0;
    int en=len;
    while(st<en){
        int mid=(st+en)/2;
        if(a[mid]>target)
            en=mid;
        else
            st=mid+1;
    }
    return st;
}

 

직접 구현하는 binary_search, lower_idx, upper_idx를 작성해보았다. 

내부적으로 구현은 매우 유사한데 등호의 포함 여부, en=n-1 혹은 en=len 등과 같은 부분에서 차이를 보인다.

이러한 차이들이 어떠한 결과에서의 차이점을 유발하는지 이해하고 위와같은 함수들을 작성할때 신경을 써야한다. 

 

그리고 위의 함수들을 stl에 있는

binary_search(), lower_bound(a,a+n,t), upper_bound(a,a+n,t) 함수들을 이용하여서 동일한 기능으로 사용할 수 있다. 

모두 다 알고있도록 하자.