[C/C++] 이진탐색 - lower_bound, upper_bound 구현

---

구현해 보는 이유

C++ 헤더 <algorithm>에 lower_bound와 upper_bound 함수가 있다.
근데 있는 거 두고 굳이 왜 직접 구현해 보는 걸까?

이유는 총 2가지이다.

1. 학습적인 목적(이진탐색 구현)

2. 이진 탐색 변형

이 목적으로 한번 구현해 본다.

 

 

---

lower_bound와 upper_bound 메서드

---

lower_bound

lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음 나타난 곳의 인덱스를 반환한다.

예를 들어서,
{2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾는다면
배열에서 2의 인덱스인 0을 반환한다.

또한 5를 찾는다면, 처음으로 5보다 큰 6의 인덱스인 2를 반환한다.

 

---

upper_bound

upper_bound는 찾고자 하는 값보다 큰 값이 처음 나타난 곳의 인덱스를 반환한다.

lower_bound와 거의 똑같지만,
차이점은 찾고자 하는 값과 같은 값은 제외한다는 점이다.

 {2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾으면 0을 반환하겠지만,
upper_bound를 사용하여 2를 찾으면 2를 초과하는 4가 있는 인덱스 1을 반환한다.

 

 

---

코드로 구현하기

#include <stdio.h>

#define SIZE 10

// lower_bound 구현
int my_lower_bound(int arr[], int num){
    int start = 0;
    int end = SIZE-1;
    int mid;
	// 찾는 값이 배열의 가장 큰 수보다 큰 경우 실패
    if(num > arr[end]) return -1;
    
    int findIdx = SIZE-1; // 찾아야 하는 수의 인덱스
    
    // 이진 탐색 사용
    while(start <= end){
        mid = (start+end)/2;
        
        // 찾아야하는 수가 arr[mid]보다 더 작을 때
        if(arr[mid] > num) {
            end = mid-1;
            findIdx = mid; // 해당 값을 findIdx로 지정
        }
        // 찾아야하는 수가 arr[mid]보다 더 클때
        else if(arr[mid] < num) start = mid+1;
        
        // 찾아야하는 수와 해당 배열의 수가 같을 때
        else {
            findIdx = mid;
            break;
        }
    }
    return findIdx;
}


// upper_bound 구현
int my_upper_bound(int arr[], int num){
    int start = 0;
    int end = SIZE-1;
    int mid;

    if(num > arr[end]) return -1;
    int findIdx = SIZE-1;
    while(start <= end){
        mid = (start+end)/2;
        if(arr[mid] > num) {
            end = mid-1;
            findIdx = mid;
        }
        // upper_bound는 같은 것도 취급해줘야함
        else if(arr[mid] <= num) start = mid+1;
    }
    return findIdx;
}



int main(){
    int input = 15;
    int arr[] = {1,4,5,6,8,9,10,15,20,40};

    printf("lower_bound : %d\n",my_lower_bound(arr,input));
    printf("upper_bound : %d\n",my_upper_bound(arr,input));

}

출력

C/C++로 구현한 lower_bound와 upper_bound 함수이다.

두 함수 모두 이진 탐색을 베이스로 탐색을 진행하기 때문에, 탐색을 이진 탐색으로 진행해 준다.

물론 이진탐색을 진행하기 위해서
탐색할 배열은 오름차순 정렬이 되어있는 상태이다.

upper_boun와 lower_bound로 15를 찾았을 때
정상적으로 15와 20을 찾는 것을 확인할 수 있다.

가끔씩 우리가 자주 사용하고 있는
함수를 직접 구현해 보는 것도 좋은 학습이 되는 것 같다.