Algorithm Guidecomplexity: O(log n)

이진 탐색 (Binary Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Binary Search

이진 탐색 시작. 정렬된 배열을 결정 트리로 표현하면 각 노드가 해당 반복의 mid 원소가 됩니다.

Logic Node1 / 7

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

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