Binary Search 알고리즘

이진 탐색(Binary Search)란?

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 매우 빠르게 찾아내는 알고리즘입니다. 일상생활에서 전화번호부나 사전에서 단어를 찾을 때 중간쯤을 펼쳐보는 것과 같은 원리라고 생각하면 이해하기 쉽습니다.

핵심 원리: "반씩 버리기"

이진 탐색의 가장 중요한 전제 조건은 데이터가 반드시 오름차순이나 내림차순으로 정렬되어 있어야 한다는 것입니다.

작동 방식은 다음과 같습니다:

1. 데이터의 중간값을 선택합니다.
2. 중간값과 내가 찾으려는 값을 비교합니다.
3. 값이 같다면? 탐색 종료!
4. 중간값보다 크다면? 중간값 기준 오른쪽(큰 쪽)만 남기고 왼쪽은 버립니다.
5. 중간값보다 작다면? 중간값 기준 왼쪽(작은 쪽)만 남기고 오른쪽은 버립니다.
6. 값을 찾을 때까지 이 과정을 반복합니다.

예시로 이해하기

숫자 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]가 들어있는 리스트에서 "17"을 찾는다고 가정해 봅시다.

단계	범위	중간값	비교 결과	다음 조치
1단계	0~9	9(인덱스 4)	17 > 9	오른쪽 절반(인덱스 5~9) 선택
2단계	5~9	15(인덱스 7)	17 > 15	오른쪽 절만(인덱스 8~9) 선택
3단계	8~9	17(인덱스 8)	17 == 17	탐색 성공

 

위 표를 살펴보면 단 3번의 비교만으로 10개의 숫자 중 원하는 값을 찾아냈습니다. 처음부터 하나씩 찾는 순차 탐색이었다면 9번을 비교해야 했을 것입니다.

이진 탐색의 시간 복잡도

이진 탐색의 효율성은 데이터가 많아질수록 빛을 발합니다. 한 번 비교할 때마다 후보군이 절반씩 사라지기 때문에 시간 복잡도는 O(log n)입니다.

파이썬 코드 예시

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 찾은 경우 인덱스 반환
        elif arr[mid] > target:
            high = mid - 1  # 왼쪽 절반 탐색
        else:
            low = mid + 1   # 오른쪽 절반 탐색
            
    return -1  # 찾지 못한 경우

이진 탐색 활용

lower bound 찾기

target 이상의 값(target보다 같거나 큰 값)이 처음 나타나는 위치를 찾는 데 아주 유용합니다.

def search_lower_bound(arr, target):
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

동작 방식

초기 상태: left = 0, right = 5 (배열 길이), arr = [1, 3, 3, 5, 8], target = 3

Step 1

• 범위: [1, 3, 3, 5, 8] (인덱스 0~4)
• mid 계산: (0 + 5) // 2 = 2 → arr[2] 값은 3
• 비교: arr[2] < 3인가? → False (3은 3보다 작지 않음)
• 결과: right = mid가 되어 right = 2가 됩니다.
• 상태: left=0, right=2 (이제 0~1번 인덱스만 봅니다.)

Step 2

• 범위: [1, 3] (인덱스 0~1)
• mid 계산: (0 + 2) // 2 = 1 → arr[1] 값은 3
• 비교: arr[1] < 3인가? → False
• 결과: right = mid가 되어 right = 1이 됩니다.
• 상태: left=0, right=1

Step 3

• 범위: [1] (인덱스 0)
• mid 계산: (0 + 1) // 2 = 0 → arr[0] 값은 1
• 비교: arr[0] < 3인가? → True (1 < 3)
• 결과: left = mid + 1이 되어 left = 1이 됩니다.
• 상태: left=1, right=1

종료 (Final)

• while left < right 조건에서 1 < 1은 False이므로 반복문이 종료됩니다.
• return left 값인 1을 반환합니다.
• 의미: 인덱스 1은 숫자 3이 처음 등장하는 위치입니다.

일반 이진 탐색 vs Lower Bound 차이점

lower bound 찾기 알고리즘이 일반적인 이진 탐색과 다른 결정적인 부분은 중복된 값이 있을 때의 처리 방식입니다.

1. right = len(arr): 탐색 범위를 배열 끝 인덱스가 아닌 '길이'로 잡습니다. 이는 target이 배열의 모든 요소보다 클 경우, 가장 마지막 인덱스 다음인 len(arr)을 반환하기 위함입니다.
2. arr[mid] < target:
   • 값이 target보다 작으면 확실히 오른쪽으로 가야 하므로 left = mid + 1.
   • 값이 target보다 크거나 같으면, 그 위치가 시작점일 가능성이 있으므로 mid를 포함하여 right = mid로 좁힙니다.
3. 최종 반환: left와 right가 만나는 지점이 곧 target이 들어갈 수 있는 가장 왼쪽 자리가 됩니다.

upper bound 찾기

Upper Bound(상한선) 알고리즘입니다. Lower Bound가 target보다 같거나 큰 수가 처음 나타나는 위치를 찾는다면, Upper Bound는 target보다 큰 값(초과)이 처음으로 나타나는 위치를 찾습니다.

def search_upper_bound(arr, target):
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) // 2
            if arr[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left

동작 방식

초기 상태: left = 0, right = 5, arr = [1, 3, 3, 5, 8], target = 3

Step 1

• 현재 범위: [1, 3, 3, 5, 8] (인덱스 0~4)
• mid 계산: (0 + 5) // 2 = 2 → arr[2] 값은 3
• 비교: arr[2] <= 3인가? → True (3은 3보다 작거나 같음)
• 결과: left = mid + 1이 되어 left = 3이 됩니다.
• 이유: 우리는 3보다 큰 값을 찾아야 하므로, 현재 값이 3이라면 그보다 오른쪽을 봐야 합니다.

Step 2

• 현재 범위: [5, 8] (인덱스 3~4)
• mid 계산: (3 + 5) // 2 = 4 → arr[4] 값은 8
• 비교: arr[4] <= 3인가? → False (8은 3보다 큼)
• 결과: right = mid가 되어 right = 4가 됩니다.
• 상태: left = 3, right = 4

Step 3

• 현재 범위: [5] (인덱스 3)
• mid 계산: (3 + 4) // 2 = 3 → arr[3] 값은 5
• 비교: arr[3] <= 3인가? → False (5는 3보다 큼)
• 결과: right = mid가 되어 right = 3이 됩니다.
• 상태: left = 3, right = 3

종료 (Final)

• while left < right 조건에서 3 < 3은 False이므로 반복문이 종료됩니다.
• return left 값인 3을 반환합니다.
• 의미: 인덱스 3은 숫자 3보다 큰 첫 번째 숫자인 5가 있는 위치입니다.

Lower Bound vs Upper Bound 비교

두 알고리즘의 차이는 딱 한 군데, if문의 비교 연산자에 있습니다.

구분	lower bound	upper bound
핵심 조건	arr[mid] < target	arr[mid] <= target
목표	target 이상의 첫 번째 위치	target 초과의 첫 번째 위치
예시 결과	3이 시작되는 인덱스 1	3이 끝난 다음 인덱스 3

이 두 알고리즘를 같이 쓰면?

이 두 알고리즘을 조합하면 정렬된 배열에서 특정 숫자가 몇 개 포함되어 있는지 아주 쉽게 알 수 있습니다.

개수 구하기 공식: upper_bound - lower_bound

• 예: 3 - 1 = 2 (숫자 3은 총 2개 존재)

예시 문제

문제 상황

• 정렬된 배열: arr = [1, 2, 4, 4, 4, 6, 7, 8, 8, 10]
• 질문: "이 배열에서 4 이상 8 이하인 숫자는 총 몇 개인가요?"

문제 해결 전략

우리는 left_limit 이상 right_limit 이하의 숫자를 세고 싶습니다. 이때 이진 탐색의 두 가지 변형을 이렇게 사용합니다.

1. Lower Bound (left_limit): left_limit이 처음 나타나는 위치를 찾습니다.
2. Upper Bound (right_limit): right_limit보다 큰 값이 처음 나타나는 위치를 찾습니다.
3. 결과: Upper Bound(right_limit) - Lower Bound(left_limit)

def count_range(arr, left_limit, right_limit):
    # 1. left_limit 이상인 값이 처음 나오는 위치 (Lower Bound)
    low_idx = search_lower_bound(arr, left_limit)
    
    # 2. right_limit보다 큰 값이 처음 나오는 위치 (Upper Bound)
    high_idx = search_upper_bound(arr, right_limit)
    
    # 두 인덱스의 차이가 곧 해당 범위 숫자의 개수입니다.
    return high_idx - low_idx

# 테스트
arr = [1, 2, 4, 4, 4, 6, 7, 8, 8, 10]
# 4 이상 8 이하의 숫자 개수 찾기
result = count_range(arr, 4, 8)
print(f"4 이상 8 이하 숫자의 개수: {result}개")

실행 과정 추적

arr = [1, 2, 4, 4, 4, 6, 7, 8, 8, 10] 에서 4 이상 8 이하를 찾는다면:

1. search_lower_bound(arr, 4) 실행:
   • 숫자 4가 처음으로 등장하는 인덱스 2를 반환합니다.
2. search_upper_bound(arr, 8) 실행:
   • 숫자 8보다 큰 숫자(10)가 처음으로 등장하는 인덱스 9를 반환합니다.
3. 최종 계산:
   • 9 (high_idx) - 2 (low_idx) = 7
   • 실제로 [4, 4, 4, 6, 7, 8, 8] 총 7개가 맞습니다!

왜 이 방식이 좋을까요?

만약 배열의 크기가 1억 개이고, 우리가 찾아야 할 범위의 숫자가 5천만 개라고 가정해 봅시다.

• 일반적인 방법: 처음부터 끝까지 돌며 숫자를 하나씩 세면 1억 번을 확인해야 합니다.
• 이진 탐색 활용: Lower Bound 찾기(약 27번) + Upper Bound 찾기(약 27번) = 단 54번의 비교만으로 끝납니다.

데이터가 많아질수록 이 차이는 비교할 수 없을 만큼 커집니다.