입꼬리 올리고 사는 개발자

안녕하세요 오늘은 이분탐색과 그의 bound 전우들에 대해 알아보겠습니다!

1. 이분탐색

이분 탐색 알고리즘(binary search algorithm)은 이진 탐색 알고리즘이라고도 불리며 

오름차순으로 정렬된 리스트(배열)에서 특정한 값의 위치를 찾는 알고리즘입니다.

그럼 예시와 함께 이분탐색의 장단점에 대해 알아보겠습니다.

운이 좋게도 정렬된 배열의 특정한 값의 위치를 찾는 가장 단순한 방법은 앞에서 부터 비교하는 것입니다

값이 10인 데이터의 위치를 찾는 다고 가정해보면

for(int i = 0; i < N; i++) {
	if(arr[i] == 16) return i;
}

0번째 원소부터 차근차근 비교해보면서 7번의 비교를 끝내고 나서야 10이 idx = 6의 위치에 있다는 것을 알 수 있습니다.

최악의 경우 크기가 N인 배열에서는 N번의 비교가 필요한 선형적인 탐색이므로 O(n)의 시간이 걸릴 것 입니다.

여기서 이분 탐색을 이용하여 더 효율적이라 볼 수 있는 O(logN)의 시간도 가능합니다.

이분 탐색의 핵심은 한 번의 비교로 데이터를 반으로 나눠(둘 이, 나눌 분 해서 이분) 우리가 고려해야 할 구간의 크기를 반으로 줄이는 것입니다.

이제 10의 위치를 이분 탐색을 통하여 찾아봅시다!!

먼저 배열의 가장 첫번째 인덱스를 low(고려해야 할 구간의 처음), 가장 마지막 인덱스를 high(고려해야할 구간의 끝)로 설정해줍니다.

그 후 그 가운데 인덱스인 (low + high)  / 2  를 mid로 지정해 줍니다. 예시의 경우에는 4가 되겠습니다.

그 후 arr[mid]값과 우리가 찾고 있는 값의 대소 비교를 해줍니다.

arr[mid]값인 6은 우리가 찾는 값은 10보다 작습니다. 그리고 low부터 mid 까지의 값은 모두 6보다 작거나 같은 값들입니다.

이 의미는 low부터 mid까지의 값들은 모두 10보다도 작을 것이기 때문에 이 구간은 10이 있을 수 없다는 것입니다.

이제 필요없는 구간들을 제외하고 탐색할 구간을 재설정 해 줍니다.

고려해야할 구간의 처음인 low를  mid의 바로 오른쪽인 mid + 1로, 고려해야할 구간의 가장 끝인 high는 그대로 둡니다.

또 다시 mid는 중간에 위치한 값인 (low + high) / 2 로 설정해 줍니다.

우리는 이 과정을 arr[mid]가 찾는 값(10)이 나올 때 까지 반복해줄 것입니다.

이번의 arr[mid]값인 13은 우리가 찾는 10보다 크기 때문에 mid부터 오른쪽 값들은 10이 없는 것이 확정입니다.

이제 다시 low는 5 그대로 high는 6으로 설정해 준 뒤 mid는 (5 + 6) / 2 인 5로 설정해줍니다.

arr[mid]값인 8이 10보다 작으므로 low부터 mid까지의 구간을 폐쇄하고 low를 6 high를 6 mid를 (6 + 6) / 2인 6으로 재설정합니다.

우리가 찾는 값인 10이 arr[mid]와 일치하므로 10의 위치는 idx = 6이었습니다.

이와 같이 이분탐색은 low, high, mid를 재설정해주며 고려해야할 구간을 줄여가고

최종적으로는 arr[mid] = 찾는 값이 되는 mid를 찾는 알고리즘입니다.

코드는 이러합니다.

int binarySearch(int arr[], int low, int high, int target){
    while(low <= high){
        int mid = (low + high) / 2;
        if(arr[mid] == target) return mid;
        //target보다 크다면 오른쪽 구간은 필요없음
        if(arr[mid] > target) high = mid - 1;
        //target보다 작다면 왼쪽 구간은 필요없음
        else low = mid + 1;
    }
    return -1;
}

이분탐색의 장점 - 원하는 원소를 O(log n) 시간에 찾을 수 있다.

이분탐색의 단점 - 정렬된 리스트에만 사용할 수 있다(정렬도 O(log n)이라 생각하면 시간복잡도의 변화는 없다)

2. Upper Bound & Lower Bound

이분 탐색은 특정한 한 데이터를 찾는 데에 좋지만 우리 실생활에서는 한번에 여러 데이터가 필요할 때가 있습니다.

예를 들어 상대평가로 학점 컷을 나눌 때 90점 이상인 학생 모두를 A로 하려 한다든가

중복이 허용되는 데이터에서 생일이 9월 22일인 모든 데이터가 필요한 경우 등등이 있습니다.(이분 탐색은 9월 22일이 생일인 데이터, 즉 인덱스 하나만을 반환함).

이런 경우들은 이분 탐색의 Bound 형제들이 요긴하게 쓰입니다.

Upper Bound는 특정 값 '초과'의 값이 처음으로 나타나는 위치를 뜻하며

Lower Bound는 특정 값 '이상'의 값이 처음으로 나타나는 위치를 뜻합니다.

이런 리스트에서 '1' 이란 값의 Upper Bound와 Lower Bound를 찾는다면

Upper Bound는 '1' 초과인 값이 처음으로 나타나는 '3'의 위치인 5

Lower Bound는 '1' 이상인 값이 처음으로 나타나는 '1'의 위치 2입니다.

'5'라는 값의 Upper Bound와 Lower Bound도 찾아보죠

Upper Bound는 '5' 초과인 값이 처음으로 나타나는 '6'의 위치인 8

Lower Bound는 '5' 이상인 값이 처음으로 나타나는 '6'의 위치 8입니다.

이처럼 Upper Bound와 Lower Bound는 서로 같을 수도 있습니다.

이를 활용하는 방법은 여러가지가 있습니다.

값이 1을 초과하는 데이터들 ->1의 Upper Bound 부터 데이터 끝까지

값이 5 미만의 데이터 -> 0 부터 5의 Lower Bound - 1 까지

값이 1인 데이터들 -> 1의 Lower Bound부터 1의 Upper Bound - 1까지

등등이 있겠습니다

찾는 과정은 이분탐색과 상당히 흡사하기 때문에 코드와 주석으로 대체하겠습니다.

초과, 이상의 차이인 만큼 조건문의 등호 하나만 차이가 나는 것을 볼 수 있습니다.

int UpperBound(int arr[], int low, int high, int target){
    while(low < high){
        int mid = (low + high) / 2;
        //arr[mid]값이 target 초과라면 high 뒤의 값들은 최초로 초과이진 않을 것임 
        if(arr[mid] > target) high = mid;
        //arr[mid]값이 target 이하라면 low부터 mid까지는 모두 target 이하일 것임
        else low = mid + 1;
    }
    //구간 내의 모든 값이 target 이하라면 마지막 + 1 위치 반환
    return high + 1;
}

int LowerBound(int arr[], int low, int high, int target){
    while(low < high){
        int mid = (low + high) / 2;
        //arr[mid]값이 target 이상이라면 high 뒤의 값들은 최초로 이상이진 않을 것임 
        if(arr[mid] >= target) high = mid;
        //arr[mid]값이 target 미만이라면 low부터 mid까지는 모두 target 미만일 것임
        else low = mid + 1;
    }
    //구간 내의 모든 값이 target 미만이라면 마지막 + 1 위치 반환
    return high + 1;
}

* 개인적인 팁이라면 리스트 전체를 탐색하기 위해서는 high를 N-1이 아닌 N으로 설정하는 것이 좋습니다.

1.  만약 끝값이 배열 내 유일한 7이라고 했을 때 7의 Lower Bound는 N-1, Upper Bound가 N이 나오게끔 설정하는 방법

2. N이 mid값이 되는 경우는 절대 존재할 수 없으므로 seg fault도 일어나지 않음.

Upper Bound와 Lower Bound는 <Algorithm> 헤더에도 구현되어 있습니다.

정렬은 필수로 해주시고 이 함수들은 주소값 자체를 반환하기 때문에 arr[0]의 주소값을 빼주셔야 인덱스를 구할 수 있습니다.

추가로 배열 내에 Upper Bound, Lower Bound가 존재하지 않는 경우는 N을 반환합니다.

upper_bound(arr, arr + N, target) - arr  

lower_bound(arr, arr + N, target) - arr  

https://cplusplus.com/reference/algorithm/upper_bound/

https://cplusplus.com/reference/algorithm/lower_bound/

* 표시된 팁이 알고리즘 문제들 풀 때 알짜배기라고 생각합니다.

이번 주도 화이팅입니다!!