[Python] Algorithm #03: 이분 탐색 (Binary Search)

이번 글에서는 정렬을 간단히 짚고, 이분 탐색을 중심으로 다룹니다.

 

정렬은 이분 탐색을 위한 전제 조건이 되는 경우가 많습니다.

그래서 정렬 자체는 짧게 보고, 이분 탐색의 원리와 활용에 더 집중해보겠습니다.

 

정렬에 대한 세부적인 내용은 기초 트랙을 참고하시면 되겠습니다.

[Python] Basic #03: 정렬

[Python] Basic #03: 정렬

---

1. 정렬은 왜 필요한가

이분 탐색은 정렬된 데이터에서만 제대로 사용할 수 있습니다.

데이터가 정렬되어 있어야 가운데 값을 기준으로 왼쪽과 오른쪽 중 어디를 버릴지 판단할 수 있기 때문입니다.

nums = [5, 2, 9, 1, 3]

nums.sort()
print(nums)  # [1, 2, 3, 5, 9]

result = sorted(nums)
print(result)  # [1, 2, 3, 5, 9]

• sort()는 원본 리스트를 바꾸고, sorted()는 새로운 리스트를 반환합니다.

이분 탐색을 할 데이터는 보통 먼저 정렬해 둡니다.

---

2. 이분 탐색의 기본 원리

이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 방법입니다.

 

가운데 값을 확인한 뒤, 찾는 값이 더 작으면 왼쪽, 더 크면 오른쪽만 남기고 탐색 범위를 절반씩 줄입니다.

배열이 정렬 되어있기에 크기 비교를 통해 가능합니다.

 

시간복잡도는 O(log n)입니다.

매번 탐색 범위가 절반으로 줄어들기 때문에 데이터가 커질수록 효율이 좋습니다.

nums = [1, 2, 3, 5, 9]
target = 5

left = 0
right = len(nums) - 1
found = False

while (left <= right):
    mid = (left + right) // 2

    if (nums[mid] == target):
        found = True
        break
        
    elif (nums[mid] < target):
        left = mid + 1
        
    else:
        right = mid - 1

print(found)  # True

---

3. 직접 구현하는 이분 탐색

코딩테스트에서는 이분 탐색을 직접 구현할 수 있어야 합니다.

반복문으로 구현하면 이해하기 쉽고, 범위를 직접 제어하기도 편합니다.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while (left <= right):
        mid = (left + right) // 2

        if (arr[mid] == target):
            return mid
            
        elif (arr[mid] < target):
            left = mid + 1
            
        else:
            right = mid - 1

    return -1

nums = [1, 2, 3, 5, 9]

print(binary_search(nums, 3))  # 2
print(binary_search(nums, 4))  # -1

• 반환값을 True/False로 둘 수도 있고, 위치 인덱스로 둘 수도 있습니다.

---

4. bisect 모듈 활용

Python에서는 bisect 모듈을 사용하면 정렬된 리스트에서 위치를 쉽게 찾을 수 있습니다.

 

bisect_left()는 삽입될 왼쪽 위치를, bisect_right()는 오른쪽 위치를 반환합니다.

import bisect

nums = [1, 2, 2, 2, 3, 5]

left = bisect.bisect_left(nums, 2)
right = bisect.bisect_right(nums, 2)

print(left)   # 1
print(right)  # 4

• bisect_left()와 bisect_right()는 같은 값이 여러 개 있을 때 유용합니다.
• 첫 등장 위치와 마지막 다음 위치를 구할 수 있기 때문입니다.

---

5. 이분 탐색 응용

이분 탐색은 단순히 값을 찾는 것뿐 아니라, 조건을 만족하는 최소값이나 최대값을 찾는 데도 자주 쓰입니다.

 

예를 들어 “이 값 이상이 처음 나오는 위치”를 찾는 문제는 정렬과 이분 탐색을 함께 활용하면 쉽게 풀 수 있습니다.

import bisect

scores = [10, 20, 20, 35, 40, 50]
target = 20

idx = bisect.bisect_left(scores, target)
print(idx)  # 1

if (idx < len(scores)):
    print(scores[idx])  # 20

• 이런 방식은 중복 원소가 있는 배열, 점수 기준 필터링, 구간 탐색 문제에서 자주 등장합니다.

---

6. 자주 하는 실수/주의점

• 이분 탐색은 정렬된 데이터에서만 사용할 수 있습니다.
• 중간값은 보통 (left + right) // 2로 구합니다.
• left, right 갱신을 잘못하면 무한 루프가 생길 수 있습니다.
• bisect_left()와 bisect_right()의 차이를 구분해야 합니다.
• 중복 값이 있을 때는 “찾는다”보다 “어디에 들어가는가”를 기준으로 생각하면 편합니다.

---

7. 종합 예제

아래 예시는 학생 점수 목록에서 특정 점수가 처음 등장하는 위치를 찾는 예제입니다.

import bisect

scores = [45, 50, 50, 60, 70, 80, 80, 90]
target = 80

# target이 들어갈 가장 왼쪽 위치
idx = bisect.bisect_left(scores, target)

if (idx < len(scores) and scores[idx] == target):
    print(idx)  # 5
    
else:
    print(-1)

• 직접 구현한 이분 탐색과 bisect의 역할을 모두 알고 있으면, 문제에 따라 더 빠르게 선택할 수 있습니다.

---

8. 종합 요약

• 정렬: 이분 탐색의 전제 조건
• 이분 탐색: 정렬된 데이터에서 범위를 절반씩 줄이며 탐색
• 시간복잡도: O(log n)
• bisect_left(): 왼쪽 삽입 위치
• bisect_right(): 오른쪽 삽입 위치
• 반복문 구현: 코딩테스트에서 자주 사용