[Algorithm] 이분 탐색 (Binary Search) 와 upper_bound, lower

이분 탐색 (Binary Search)

이분 탐색은 정렬되어 있는 배열에서 원하는 값을 찾는데에 있어서, 순서대로 찾는 방식이 아닌 두 부분으로 분할해서 찾는 방식이다. 아래 그림을 보자.

arr[0] = 1, arr[1] = 2 ... arr[6] = 7인 배열이라고 가정한다.

만약 6이라는 값을 찾고 싶다고 가정해보자. 순차적으로 찾는다면 처음부터 1 - 2 - 3 - 4 - 5 - 6 으로 6번만에 찾을 수 있다. 그런데 만약 배열의 길이가 억 단위가 넘어간다고 생각해보자. (물론 억 단위의 배열을 사용할 일은 없기는 하다.) 그리고 찾고자 하는 수가 맨 마지막에 있다고 치면 그 배열의 길이 만큼 전부 탐색을 해야하기 때문에 시간이 매우 오래 걸리게 된다. 이럴 경우 이분 탐색을 이용하여 시간을 단축시킬 수 있다.

이분 탐색의 기본적인 개념은 중앙값을 기준으로 좌우를 탐색하여, 찾고자 하는 값이 왼쪽에 있는지 오른쪽에 있는지 탐색하는 것이다. 이 때 중요한 것은 이분 탐색을 이용할 배열은 '정렬되어 있는 배열' 이어야만 한다. 이분 탐색을 이용하여 위의 배열에서 6을 찾아보자.

참고로 안에 적혀진 값은 인덱스가 아닌 배열에 들어있는 값이다! 그림 밑의 캡션에서 보기 편하게 arr[0] = 1, arr[1] = 2, ... arr[6] = 7로 정해놨다. 이 형태를 잘 보고 넘어가자.

1. 중앙 인덱스를 0 과 6의 가운데인 3로 정한다.

중앙값을 맨 처음의 index와 맨 마지막의 index의 중앙으로 정해준다. 즉 맨 처음의 index = left, 맨 마지막의 index = right, 중앙값을 mid라고 정할 때, 중앙값 mid = (left + right) / 2가 된다.

2. 목표값이 중앙값보다 큰지 작은지 확인한다.

찾고자 하는 목표값(val)이 중앙값(arr[mid])보다 크면 왼쪽 기준 인덱스인 left를 중앙 인덱스 기준 오른쪽으로 한칸 이동하고, 찾고자 하는 목표값이 중앙값보다 작다면 오른쪽 기준 인덱스인 right를 중앙 인덱스 기준 왼쪽으로 한칸 이동한다. 이게 무슨 이야기냐, 그림으로 표현하면 아래와 같다.

1) 목표값이 중앙값보다 클 때

목표값이 중앙값보다 더 크다면 탐색 범위를 중앙값 기준 오른쪽으로 새로 잡아준다. 탐색 범위가 이전에는 left (0) < range < right (6) 였다면 탐색 범위를 새로 잡아서 mid + 1 (4) < range < right (6) 가 된다. 따라서 left = mid + 1 로 바꿔준다. 이렇게 하면 인덱스가 4, 5, 6 인 것 중에서 찾게 된다.

2) 목표값이 중앙값보다 작을 때

마찬가지로 left (0) < range < right (6) 에서 left (0) < range < mid - 1 (2)로 잡아준다. 즉 right = mid - 1 이 된다. 이렇게 하면 인덱스가 0, 1, 2인 것 중에서 찾게 된다.

이 때 우리는 목표값 goal = 6인 것을 찾는 것이므로 목표값이 중앙값보다 큰 경우가 된다. 따라서 1) 의 기준으로 탐색 범위를 바꿔준다.

3. 목표값에 도달할 때 까지 반복해준다.

위 과정에서 우리의 목표값인 6에 도달하지 않았기 때문에 해당 과정을 반복해줘야한다. 처음 중앙값 오른쪽을 기준으로 탐색하므로 탐색 인덱스는 4, 5, 6이며 새로운 중앙값을 다시 정해준다면 맨 왼쪽인 4와 맨 오른쪽인 6의 중앙인 5가 중앙 인덱스가 된다. 즉 left = 4, mid = 5, right = 6 이다.

이 때 arr[mid] = arr[5] = 6이므로 목표값 goal = 6 과 일치하게 된다. 목표값을 찾았을 경우 이분 탐색을 종료한다. 만약 못 찾았을 경우 다시 새로운 중앙값을 선언해서 이분 탐색을 반복해주면 된다.

만약 위에서 목표값 goal = 5인 경우를 찾는다면 arr[mid] > goal 이므로 left = 4, right = mid - 1 = 5 - 1 = 4로 지정해서 mid = (left + right) / 2 = (4 + 4) / 2 = 4 로 다시 지정해서 탐색하게 되는 것이다.

이분 탐색 구현

프로그램 개발에 따라, 또는 코딩 테스트일 경우 문제에 따라 이분 탐색의 형태가 조금씩 다르겠지만, 기본적인 형태는 다음과 같다.

#include <stdio.h>
#include <iostream>

using namespace std;

int binary_search(int arr[], int left, int right, int goal){

    while(left <= right){
        int mid = (left + right) / 2;
        if(arr[mid] < goal){
            left = mid + 1;
        }
        else if(arr[mid] > goal){
            right = mid - 1;
        }
        else if(arr[mid] == goal){
            return mid;
        }
    }
}

upper_bound 와 lower_bound

그렇다면 upper_bound와 lower_bound는 뭐길래 이분 탐색과 연관되서 나왔을까? 어떤 정렬된 배열에서 찾고자 하는 값이 1개일 경우도 있지만, 당연히 여러 개가 나올 경우도 존재한다. lower_bound는 찾고자 하는 값 이상이 처음 나타나는 위치를 찾는 것이며, upper_bound는 찾고자 하는 값보다 큰 값이 처음으로 나오는 위치를 찾는 것이다. 예를 들어,

{1, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 7, 8, 8, 9, 9, 9, 10}

위의 배열에서 5라는 값을 찾는다고 생각해보자. 그런데 5는 7번부터 10번까지 동일한 값이 존재한다. 단순히 이분 탐색을 진행한다면 7, 8, 9, 10번 중에서 하나를 return하고 종료할 것이다. 하지만 5가 존재하는 인덱스는 4개이므로 1개만 return 한다면 틀린 결과가 된다. 즉 우리는 "7번부터 10번까지 입니다." 라는 결과를 원하는데, 이 때 lower_bound (7) <= result < upper_bound (11) 이 되는 것이다. 물론 쓰임새에 따라 lower_bound를 찾는 값보다 작은 값으로 설정할지 포함할지 혹은 upper_bound를 찾는 값보다 큰 값으로 설정할지 또는 포함할지 본인의 입맛에 맞게 구현할 수 있다.

일단 기본적으로 lower_bound & upper_bound는 아래와 같이 구현할 수 있다.

#include <stdio.h>
#include <iostream>

using namespace std;

long long lower_bound(int arr[], int n, int key){
    int start = 0; int end = n;
    while(end - start > 0){
        int mid = (start + end) / 2;
        if(arr[mid] < key){
            start = mid + 1;
        }
        else if(arr[mid] >= key){
            end = mid;
        }
    }
    return end;
}

long long upper_bound(int arr[], int n, int key){
    int start = 0; int end = n;
    while(end - start > 0){
        int mid = (start + end) / 2;
        if(arr[mid] <= key){
            start = mid + 1;
        }
        else if(arr[mid] > key){
            end = mid;
        }
    }
    return end;
}

이분 탐색과 별로 다르지 않는데, lower_bound는 현재값이 찾고자 하는 값보다 작을 때 가리키는 위치가 감소하게 되며, upper_bound는 현재값이 찾고자 하는 값보다 작거나 같을 때 가리키는 위치가 오른쪽으로 이동하게 되어 범위를 찾게 된다. 위의 배열을 보면서 머릿 속으로 이동시켜보면서 이해해보도록 하자.

Cat On The Keyboard

이 블로그 검색