Binary Search (Lower Bound, Upper Bound)

Binary Search

 

•  배열에서 원하는 값의 위치를 O(log N) 만에 찾는 방법 ⇔ 순차탐색 O(N)
• 배열 내 원소가 정렬된 경우에만 사용 가능
• 정렬되지 않은 배열의 경우, 찾고자 하는 숫자의 개수가 적다면 순차탐색이 빠를 수 있음

아래는 찾고자 하는 값이 없는 경우 -1을, 있는 경우에는 해당 위치를 반환해주는 Binary Search 코드이다.

up/down 게임과 유사한 방식으로 원하는 값의 위치를 찾아가는 것을 볼 수 있다.

 

int binary_search(int target){
    int low=1, mid, high=n;
    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid]==target) return mid;
        if(arr[mid]<target) low = mid+1;
        else high = mid-1;
    }
    return -1;
}    

 

만약 정렬된 배열 내 원소들의 중복이 허용되는 경우,
✔️ target 값이 최초로 등장하는 위치가 알고 싶다면?!
✔️ target 값이 마지막으로 등장하는 위치가 알고 싶다면?!
아래를 참고하자😋

 

Lower Bound

원하는 값(target) 이상의 값이 최초로 나오는 위치를 Lower Bound 라고 하고,

binary_search() 함수를 조금 변형하여 Lower Bound를 얻을 수 있다.

 

int lower_bound(int target){
    int lower = n;
    int low=0, mid, high=n-1;
    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid]>=target){ // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 high를 변경
            high = mid-1;
            lower = min(lower, mid);
        }
        else low = mid+1;
    }
    return lower;
}

 

Upper Bound

원하는 값(target)을 초과하는 값이 최초로 나오는 위치를 Upper Bound 라고 하고,

binary_search() 함수를 조금 변형하여 Upper Bound를 얻을 수 있다.

 

int upper_bound(int target){
    int upper = n;
    int low=0, mid, high=n-1;
    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid]>target){ // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 high를 변경
            high = mid-1;
            upper = min(upper, mid);
        }
        else low = mid+1;
    }
    return upper;
}

 

Custom Bound

원하는 값(target) 보다 같거나 작은 숫자들이 있는 위치 중 가장 큰 위치를 Custom Bound 라고 하고,

binary_search() 함수를 조금 변형하여 Custom Bound를 얻을 수 있다.

 

int upper_bound(int target){
    int custom = -1;
    int low=0, mid, high=n-1;
    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid]<=target){ // 오른쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 low를 변경
            low = mid+1;
            custom = max(custom, mid);
        }
        else high = mid-1;
    }
    return custom;
}