이진 탐색

탐색이라 함은, 데이터의 집합 중에서 원하는 값을 찾는 것을 의미합니다.

오늘 다루어 볼 내용은 이진 탐색 (binary serach)인데, 이에 앞서 가장 기본적인 탐색 방법인 순차 탐색을 다루고자 합니다.

순차 탐색

순차 탐색 (sequential search)는 배열 내의 특정 데이터를 찾기 위해 앞에서부터 순차적으로 확인하는 방법입니다.

정렬되지 않은 배열에서 데이터를 찾을 때, 시간만 충분하다면 순차 탐색이 좋은 방법이 될 수 있습니다.

'Carrot' 이라는 문자열을 찾는 과정입니다.

파란색은 현재 'Carrot'와 비교하는 문자열, 빨간색은 이미 비교하였으며 일치하지 않은 문자열, 초록색은 목표로 하는 문자열입니다.

첫 번째 문자열 'Apple', 두 번째 문자열 'Banana'는 일치하지 않으므로 그 다음 문자열로 이동하고, 세 번째 문자열 'Carrot' 는 일치하므로 탐색을 종료합니다.

이렇듯 구조도 간단하고, 구현하기 쉬운 순차 탐색은 실제로 자주 사용됩니다.

배열 내에서 특정 데이터의 개수를 셀 때도 순차 탐색을 이용하기도 합니다.

데이터의 개수가 N개일 때, 최악의 경우 배열의 맨 끝까지 확인하여야 하므로, N번의 비교 연산을 하게 됩니다.

따라서 순차 탐색의 시간 복잡도는 O(N)이 됩니다.

이진 탐색

이진 탐색은 앞서 살펴본 순차 탐색과는 달리, 배열이 이미 정렬되어 있음이 전제되어야 합니다. 앞서 글에서 다루었던 정렬을 이진 탐색에 활용하게 됩니다.

조건이 전제되는 만큼, 원하는 데이터를 순차 탐색에 비하여 매우 빠르게 탐색할 수 있습니다.

이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하게 됩니다. 변수 3개를 사용하게 되는데, 탐색하고자 하는 범위 (주로 배열)의 시작점, 끝점, 그리고 중간점입니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 비교하고, 시작점과 끝점을 계속 좁혀 나가게 됩니다.

다음의 예시를 들어 살펴보겠습니다. 이미 정렬된 배열에서 숫자 4를 찾으려고 합니다. 이때 원소의 개수 N = 10입니다.

단계 1

위 표에서, 윗 줄은 배열의 인덱스이며, 아랫줄은 데이터입니다. 즉 array[2] = 4, array[0] = 0, array[9] = 18... 등이 됩니다.

시작점은 0번 인덱스, 끝점은 9번 인덱스가 되며, 중간값은 (끝점-시작점) / 2, 즉 (9 - 0) / 2 = 4.5가 됩니다. 소수점은 버리고, 4번 인덱스가 중간점이 됩니다.

찾으려는 데이터는 4입니다. 이를 중간점의 데이터 8과 비교해 보면, 4 < 8 임을 알 수 있습니다. 데이터가 일치하지 않고, 4는 8보다 작으므로, 중간점~끝점 사이의 데이터는 더 비교하지 않아도 됩니다.

단계 2

시작점과 끝점을 갱신합니다. 이미 정렬되어 있는 배열 내에서, 단계 1에서의 중간값 8보다 찾으려는 값 4는 작으므로, 1단계서의 배열 중 인덱스 0~3만을 탐색 범위에 넣습니다.

따라서 새로운 시작점은 0번 인덱스, 끝점은 3번 인덱스, 중간점 인덱스는 (3+0) / 2 = 1번 인덱스가 됩니다.

이제 찾으려는 값 4와 중간점 인덱스가 가리키는 값을 비교해 봅니다.

array[1] = 2 이므로, 찾으려는 값 4보다 작습니다. 이에 맞추어 탐색 범위를 다시 좁혀 봅니다.

단계 3

이번에는 시작점이 2번 인덱스, 끝점이 3번 인덱스가 되었고, 중간점은 (3+2) / 2 = 2번 인덱스가 되었습니다.

찾으려는 숫자 4와 array[2]를 비교해 보면, array[2] = 4이므로 탐색이 종료됩니다.

위의 예와 같이, 10개의 데이터가 있었지만 3번의 비교연산만으로 원하는 데이터를 찾았습니다.

매 단계를 거칠 때마다, 확인해야 하는 원소의 수가 절반으로 줄어듭니다.

N = 64라면, 3단계만 거쳐도 8개 가량의 데이터만 비교군에 남게 됩니다. 이렇듯, 이진 탐색의 시간 복잡도는 O(log N)이 됩니다.

이진 탐색은 크게 두 가지 방법으로 구현할 수 있습니다. 재귀 함수로 구현할 수도 있고, 반복문으로 구현할 수도 있습니다.

int binary_search(int start, int end, int target) {
    int mid = (end + start) / 2;
    if (target == array[mid])
        return mid;
    else if (start == end && array[mid] != target)
        return -1;
    else if (array[mid] > target)
        return binary_search(start, mid-1, target);
    else if (array[mid] < target)
        return binary_search(mid+1, end, target);
    else
        return -1;
}

재귀함수로 구현한 이진 탐색 알고리즘입니다.

이진 탐색은 코딩 테스트에서도 아주 중요한 알고리즘입니다. 이진 탐색의 원리는 다른 알고리즘에서도 자주 사용되며, 이진 탐색과 다른 알고리즘을 같이 묻는 문제가 나오기도 합니다. 따라서 이진 탐색 알고리즘을 코드로 수월하게 적어낼 수 있으면 큰 도움이 됩니다.

또한, 탐색 범위가 큰 경우, 예를 들어 N = 20,000,000 이상인 경우 이진 탐색으로 접근해 본다면 수행 시간에서 큰 이득을 볼 수 있을 것입니다.

이진 탐색의 전제 조건은 데이터의 정렬입니다. 이를 효과적으로 수행할 수 있는 이진 트리 자료구조를 함께 이용하면 큰 도움이 됩니다.

이진 트리는 다음에 기회가 되면 더 자세히 다루기로 하겠습니다.

*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020)" 를 참고하여 작성하였습니다.