이분 탐색 (Binary Search) 기법

숫자로 된 ID가 백만 개가 오름차순으로 정렬되어 있다. 만약 특정 ID를 찾고 싶다면 어떻게 해야 할까? 처음부터 끝까지 하나하나 찾는다고 가정하면, 맨 마지막에 있는 ID를 찾을 때 최소 백만 번은 대조해야 한다. 이렇게 하나하나 찾는 경우 매우 비효율적인 상황에 직면하게 된다. 이번 글에서는 이러한 문제를 효과적으로 해결하는 이분탐색 기법에 대해 살펴보겠다.

 

1. 이분탐색이란 무엇인가?

이분탐색이란 정렬된 배열에서 목표값을 찾기 위해 탐색 범위를 반으로 나누어가며 진행하는 알고리즘이다. 

 

이분탐색의 핵심은 다음과 같다. 정렬된 배열의 중간 지점을 확인하고, 찾는 값이 중간값보다 크다면 중간값의 오른쪽 절반만 남기고, 적다면 왼쪽 절반만 남긴다. 그리고 남은 범위에서 다시 중간지점을 확인하는 과정을 반복한다. 이렇게 탐색 범위를 계속 절반씩 줄여나가다 보면 결국 찾는 값을 발견하거나 존재하지 않음을 알게 되는 것이다.

 

이러한 이분 탐색이 작동하기 위한 중요한 전제조건은 "배열이 정렬되어 있어야"한다는 것이다.

 

단순하지만 이분탐색은 엄청난 효율성을 자랑한다. 처음부터 끝까지 하나하나 확인하는 방법을 선형검색이라고 하는데, 이에 비해 매우 빠른 속도로 답을 찾을 수 있기 때문이다.

 

2. 이분탐색의 작동 원리

이분탐색이 어떻게 작동하는지 구체적인 예시를 통해 살펴보자.

 

다음 같이 1부터 100까지의 숫자가 오름차순으로 정렬된 배열이 있다고 가정해보자.

 

[1, 5, 7, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

 

이 배열에서 숫자 55을 찾기 위해 이분 탐색을 수행해보자.

 

1단계: 초기 범위 설정

탐색 범위의 시작점(left)을 0, 끝점(right)을 21로 설정한다. 그리고 중간 지점(mid)을 계산한다.

 

mid = (0 + 21) / 2  = 10

 

배열의 인덱스 10에 있는 값은 45이다. 우리가 찾는 값 55와 비교하면, 55 > 45이므로 55는 중간값보다 오른쪽에 있다. 따라서 left를 mid + 1 = 11로 이동시킨다. 현재 left = 11, right = 21이다.

 

2단계: 범위 축소

이제 탐색 범위는 11부터 21까지다. 다시 중간 지점을 계산한다. 

 

mid = (11 + 21) / 2 = 16

 

배열의 인덱스 16에 있는 값은 75다. 우리가 찾는 값 55와 비교하면, 55 < 75이므로 55는 중간값보다 왼쪽에 있다. 따라서 right를 mid -1로 한다. mid -1 = 15로 이동시킨다. 현재 left = 11, right = 15이다.

 

3단계: 범위 다시 축소

이제 탐색 범위는 인덱스 11부터 15이다. 다시 중간 지점을 계산한다. 

 

mid = (11 + 15) / 2 = 13

 

배열의 인덱스 13에 있는 값은 60이다. 우리가 찾는 값 55와 비교하면 55 < 60이므로 55는 중간값보다 왼쪽에 있다. 따라서 right를 mid - 1 = 12로 이동시킨다. 

 

4단계: 값 발견

이제 탐색 범위 인덱스는 11부터 12이다. 다시 중간 지점을 계산한다.

 

mid = (11 + 12) / 2 = 11

 

배열의 인덱스 11에 있는 값은 55이다. 우리가 찾는 값 55가 맞다. 탐색 완료다.

 

이분탐색 각 단계를 정리하면 다음과 같이 할 수 있다. 

- 탐색 범위의 중간값을 확인한다.

- 중간값이 찾는 값과 같으면 탐색을 종료한다.

- 찾는 값이 중간값보다 크면 오른쪽 절반으로 범위를 좁힌다.

- 찾는 값이 중간값보다 작으면 왼쪽 절반으로 범위를 좁힌다.

- 범위가 더 이상 좁혀질 수 없을 때까지 위 과정을 반복한다.

 

 3. 시간복잡도 분석

이분탐색의 시간복잡도를 분석해보자. 배열의 크기를 n이라고 했을 때, 이분 탐색은 탐색할 때마다 범위를 절반씩 줄여나간다. 

 

예를 들어, n = 16일 때를 생각해보자 첫 번째 비교 후 범위는 8로 줄어들고, 두 번째 비교 후에는 4, 세 번째에는 2, 네 번째에는 1이 된다. 즉, 16 → 8 → 4 → 2 → 1로 감소하는데, 이는 log_2 16 = 4번의 비교를 의미한다.

 

일반적으로, n개의 원소를 가진 배열에서 이분탐색의 시간복잡도는 O(log n)이다. 이는 선형 탐색의 O(n)과 극명한 차이점을 보인다. 

 

실제 숫자로 비교해보자. 백만 개의 ID가 정렬되어 있다면

- 선형탐색: 최악의 경우 1,000,000번의 비교

- 이분탐색: log_2 1,000,000 ≈ 20번의 비교 

 

단 20번의 비교만으로도 백만 개 중에서 원하는 ID를 찾을 수 있다는 것이다. 이는 선형탐색에 비해 약 50,000배 빠른 성능을 의미한다. 이것이 정렬된 대규모 데이터를 다룰 때 이분탐색이 필수적인 이유다.

 

4. 구현 (코드)

이분탐색을 파이썬으로 구현해보자.

 

반복문을 이용한 이분탐색

def binary_search(arr, target):
  left = 0
  right = len(arr) - 1
  
  while left <= right: # left가 right를 넘지 않을 때까지 실행하는 것이다.
    mid = (left + right) // 2
    
    if arr[mid] == target:
      return mid # 찾은 값의 인덱스 반환
    if arr[mid] < target:
      left = mid + 1 # 오른쪽 절반으로 범위 좁히기
    else:
      right = mid -1 # 왼쪽 절반으로 범위 좁히기
    
    return -1 # 찾는 값이 없으면 -1 반환

 

반복문 방식은 left와 right 포인터를 이용해 탐색 범위를 조정한다. while 루프는 left가 right보다 작거나 같을 동안 계속 반복된다. 중간값을 계산한 후, 찾는 값과 비교하여 범위를 좁혀나간다.

 

5. 주의사항 및 조건

이분탐색을 올바르게 사용하기 위해서는 반드시 지켜야 할 조건은 배열이 반드시 정렬되어 있어야 한다는 것이다. 정렬되지 않은 배열에서는 중간값과의 대소 비교가 의미를 갖지 않기 때문이다.

---

정리

이분탐색은 정렬된 배열에서 O(log n)의 시간복잡도로 탐색을 수행하는 알고리즘이다. 선형탐색의 O(n)과 비교했을 때, 백만 개의 데이터에서 약 50,000배 적은 비교 연산으로 목표값을 찾을 수 있다.

 

이분탐색의 핵심은 탐색 범위를 반으로 계속 줄여나가면서 목표값에 접근하는 것이다. 이를 위해서는 배열이 반드시 정렬되어 있어야 한다는 것이 가장 중요한 조건이다.

 

정렬된 데이터를 다루는 상황에서 이분탐색을 고려해볼 가치가 있다.