[알고리즘 이론] 이진 탐색(Binaray Search)

순차 탐색(Sequential Search)

이진 탐색을 알아보기 전에, 가장 기본적인 탐색 방법으로 데이터를 차례대로 하나씩 확인하며 탐색하는 순차 탐색이 있다.

순차 탐색은 구현이 매우 쉽고 리스트에서 특정한 값의 원소의 개수를 세는 count() 메서드도 내부적으로 순차 탐색을 이용한다. 

순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 것이 특징이다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간 복잡도는 O(N)이다.

---

이진 탐색(Binary Search)

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위 일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

이진 탐색은 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 변수로 사용하며, 찾으려는 데이터와 중간점의 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.

 

※ 이진 탐색 과정

1. 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다.
2. 찾을 데이터와 중간점의 값을 비교하여 찾을 데이터가 중간점보다 큰 경우 중간점의 오른쪽 배열을 탐색하고 중간점보다 작은 경우 중간점의 왼쪽 배열을 탐색한다.
3. 찾을 데이터와 중간점의 값이 같을 때까지 위의 과정을 반복한다.

 

이진 탐색 과정 예시

# 재귀함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
    while start <= end:
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
    return None

 

이진 탐색 시간 복잡도 분석

위의 예시에서 전체 데이터의 개수는 10개지만, 이진 탐색을 이용해 단 3번의 탐색으로 원소를 찾을 수 있었다.

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

예를 들어 데이터의 개수가 32개일 때, 이상적인 경우 한 번의 이진 탐색 과정 후에 16개의 데이터가 남게 되며 한 번 더 수행하면 8개의 데이터만 남게 된다. 즉, 단계마다 2로 나누는 것과 동일하므로 연산 횟수는 logN(밑이 2인 로그)에 비례한다.

 

코딩 테스트에서의 이진 탐색

코딩 테스트에서 이진 탐색 문제는 탐색 범위가 큰 상황에서 탐색을 가정하는 문제가 많다. 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근하는 것이 좋다. 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.

 

또한 이진 탐색은 파라메트릭 서치(Parametric Search) 유형의 문제를 해결하기 위해 주로 이용된다.

파라메트릭 서치는 최적화 문제를 결정 문제(예, 아니오로 답하는 문제)로 바꾸어 해결하는 기법이다. 

'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀나갈 수 있다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)