이진 탐색(Binary Search) 알고리즘

개요

이진 탐색(Binary Search)은 정렬된 데이터에서 중간 값을 기준으로 절반씩 범위를 줄여가며 값을 찾는 탐색 알고리즘이다. 선형 탐색보다 훨씬 빠른 **O(log n)**의 시간 복잡도를 가지며, 배열이나 리스트에서 특정 값을 빠르게 찾아야 할 때 가장 널리 쓰이는 탐색 방식 중 하나다.

---

1. 개념 및 정의

이진 탐색은 다음과 같은 절차로 작동한다:

1. 데이터가 반드시 오름차순 또는 내림차순으로 정렬되어 있어야 한다.
2. 시작점(left)과 끝점(right)을 설정하고, 중간값(mid)을 계산한다.
3. mid 위치의 값과 찾는 값을 비교한다.
   • 일치 → 탐색 성공
   • 더 작음 → right = mid - 1
   • 더 큼 → left = mid + 1
4. 범위가 좁아질 때까지 반복한다.

---

2. 동작 원리

단계	설명
1	시작 인덱스와 끝 인덱스를 설정
2	중간 인덱스를 계산: mid = (left + right) // 2
3	arr[mid]와 target을 비교
4	탐색 범위를 절반으로 줄이며 반복

정렬된 배열일 경우에만 사용할 수 있으며, 속도가 매우 빠르다.

---

3. 파이썬 구현 예시

def binary_search(arr, target):
    left, right = 0, 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

# 사용 예시
data = [1, 3, 5, 6, 8, 10, 13]
print(binary_search(data, 6))  # 출력: 3

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(log n)
공간 복잡도	O(1) (반복문) / O(log n) (재귀 사용 시)

탐색 범위를 절반씩 줄이므로 매우 빠르게 동작한다.

---

5. 특징 및 장단점

항목	설명
정렬 필요 여부	O (필수 조건)
탐색 속도	매우 빠름 (log n 수준)
구현 방식	반복 / 재귀 가능
정렬이 안 된 경우	탐색 결과 보장 X
적용 가능 자료구조	배열, 리스트 (인덱스 접근 가능해야 함)

---

6. 시각적 예시 (입력: [1, 3, 5, 6, 8, 10, 13], target: 6)

• 초기: left=0, right=6 → mid=3 (arr[3]=6) → 일치 → 인덱스 3 반환

---

7. 다른 탐색 알고리즘과 비교

알고리즘	시간 복잡도	정렬 필요	비교 횟수
선형 탐색	O(n)	불필요	많음 (최악)
이진 탐색	O(log n)	필요	매우 적음
해시 탐색	O(1) (평균)	불필요	최소 (단, 해시 구축 필요)

---

8. 활용 사례

분야	활용 예시
알고리즘 문제풀이	lower_bound / upper_bound 문제 풀이
이진 탐색 응용	파라메트릭 서치, 결정 문제 해결
라이브러리 함수	Python bisect, Java Arrays.binarySearch 등
대규모 정렬 데이터 검색	인덱싱된 로그 검색, 정렬된 데이터셋에서 빠른 조회

---

9. 결론

이진 탐색은 정렬된 배열을 탐색할 때 매우 빠르고 효율적인 알고리즘으로, 알고리즘 학습과 실전 문제풀이에서 반드시 익혀야 할 핵심 기술이다. 파라메트릭 서치, 최적화 문제, 범위 탐색 등 다양한 형태로 응용되며, 정렬 + 이진 탐색은 가장 강력한 조합 중 하나다.