이분탐색 (Binary Search)

관련 문제

문제	난이도	핵심
입국심사	Lv.3	이분탐색 기본
징검다리	Lv.4	이분탐색 응용
순위 검색	Lv.2	이분탐색 + 해시맵

---

1. 개념

이분탐색은 정렬된 배열에서 탐색 범위를 절반씩 줄여나가며 원하는 값을 찾는 방식이다.

1~100 중 57을 찾는다면?

순차탐색: 1, 2, 3 ... 57 → 최대 100번
이분탐색: 50 → 75 → 62 → 56 → 59 → 57 → 6번

정렬이 전제되어야 한다는 조건이 있지만, 탐색 속도가 O(log N)으로 훨씬 빠르다.

---

2. 동작 과정

[1, 3, 5, 7, 9, 11, 13] 에서 7을 찾는 경우

단계	left	right	mid	arr[mid]	동작
1	0	6	3	7	탐색 성공 ✅

[1, 3, 5, 7, 9, 11, 13] 에서 9를 찾는 경우

단계	left	right	mid	arr[mid]	동작
1	0	6	3	7	9 > 7 → left = mid + 1
2	4	6	5	11	9 < 11 → right = mid - 1
3	4	4	4	9	탐색 성공 ✅

---

3. 핵심 사용 패턴

기본 탐색

left = 0, right = n - 1

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

    arr[mid] == target → 탐색 성공
    arr[mid] < target  → left = mid + 1
    arr[mid] > target  → right = mid - 1

범위 탐색 (최솟값/최댓값 찾기)

조건을 만족하는 최솟값 또는 최댓값을 찾을 때 사용한다.

left = 최솟값, right = 최댓값

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

    조건 만족 → 정답 후보 저장, right = mid - 1  (최솟값 탐색)
    조건 불만족 → left = mid + 1

---

4. 핵심 포인트 2가지

반드시 정렬된 상태에서 써라

이분탐색은 정렬이 전제다. 정렬되지 않은 배열에 적용하면 틀린 결과가 나온다.

정렬 전: [3, 1, 5, 2, 4] → 이분탐색 불가
정렬 후: [1, 2, 3, 4, 5] → 이분탐색 가능

mid 계산 시 오버플로우 주의

(left + right) / 2는 left + right가 int 범위를 초과할 수 있다. 안전하게 쓰려면 left + (right - left) / 2로 계산해라.

int mid = left + (right - left) / 2;  // ✅ 안전
int mid = (left + right) / 2;         // ⚠️ 오버플로우 가능

---

5. 시간복잡도

유형	시간복잡도	비고
순차탐색	O(N)	정렬 불필요
이분탐색	O(log N)	정렬 필요
정렬 + 이분탐색	O(N log N)	정렬이 병목

N = 1,000,000 일 때 순차탐색은 최대 100만 번, 이분탐색은 최대 20번이다.

---

6. 주의사항

• 정렬 먼저 해라. 이분탐색의 전제 조건이다.
• left <= right 조건을 지켜라. <로 쓰면 마지막 원소를 탐색 못하는 경우가 생긴다.
• mid 오버플로우를 조심해라. N이 클 때 left + (right - left) / 2로 계산해라.
• 파라메트릭 서치와 구분해라. 값을 직접 찾으면 이분탐색, 조건을 만족하는 최적값을 찾으면 파라메트릭 서치다.