Algorithm Guidecomplexity: O(log n)

이진 탐색 (Binary Search)

정렬된 배열에서 중간값을 반복적으로 비교하여 탐색 범위를 반으로 줄여가는 매우 빠르고 뛰어난 성능의 검색 알고리즘입니다. 매 반복마다 후보 공간을 절반으로 축소해 로그 스케일의 비교 횟수만으로 값을 찾아냅니다.

01이진 탐색 (Binary Search)

알고리즘 작동 원리 탐색

이진 탐색을 시작합니다. 정렬된 배열의 가운데 값과 견주며 후보 구간을 절반씩 잘라냅니다. 트리의 노드 하나가 비교 한 번입니다.

구간 한가운데 값은 34입니다. 목표 45와 견줍니다.

34는 45보다 작습니다. 왼쪽 절반은 볼 필요가 없어 오른쪽 네 칸만 남깁니다.

남은 구간의 한가운데 값은 56입니다. 다시 목표와 견줍니다.

56은 45보다 큽니다. 이번엔 오른쪽을 버리고 한 칸만 남깁니다.

남은 한 칸이 45 — 목표와 일치합니다. 세 번의 비교로 끝났습니다.

탐색 완료 · 45는 인덱스 4에 있습니다. 왼쪽 서브트리는 한 번도 들여다보지 않았습니다.

Live Python

# target: 45

1def binary_search(arr, target):

# low: 0

2 low = 0

# high: 7

3 high = len(arr) - 1

4 while low <= high:

5 mid = (low + high) // 2

6 if arr[mid] == target:

7 return mid

8 elif arr[mid] < target:

9 low = mid + 1

10 else:

11 high = mid - 1

12 return -1

1 / 7

02 쉽게 이해하기

For Everyone

🔑핵심 동작

정렬된 배열의 한가운데와 비교해 볼 범위를 절반씩 버립니다.

💡쉽게 말하면

정렬된 배열에서 중간값과 비교해 탐색 범위를 매번 절반으로 줄입니다.

O(log n)으로 매우 빨라요.

📍어디에 쓰나

–정렬된 데이터 검색
–경계값 찾기

03 파이썬 구현 코드

이진 탐색 (Binary Search)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

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:
            low = mid + 1
        else:
            high = mid - 1
    return -1