이진 탐색
이진 탐색(Binary Search) 알고리즘
이진 탐색(Binary Search) 개념과 설명
1. 이진 탐색이란?
이진 탐색(Binary Search) 은 “정렬된 리스트에서 특정 값을 빠르게 찾는 알고리즘” 이다.
- 데이터를 반씩 나누면서 탐색하므로, 시간 복잡도가
O(log N)으로 매우 빠른편이다. - 순차 탐색(Linear Search,
O(N))보다 훨씬 효율적 - 조건: 탐색할 데이터가 반드시 “정렬된 상태”여야 함!
2. 이진 탐색의 동작 원리
- 배열을 정렬된 상태로 유지
- 가운데(
mid) 값을 선택 mid값이 우리가 찾는 값과 같은지 확인- 같다면 정답을 찾은 것!
- 다르다면 더 작은지(
left이동) 또는 더 큰지(right이동) 판단
- 탐색 범위를 반으로 줄여서 다시 탐색
- 값을 찾거나, 탐색할 범위가 없을 때까지 반복
3. 이진 탐색의 시간 복잡도
- 일반적인 순차 탐색은
O(N) - 하지만, 이진 탐색은
O(log N)
→ 데이터 개수가 1,000,000개 있어도log(1,000,000) ≈ 20번만 수행하면 탐색 가능!
→ 정말 빠름!
| 데이터 개수(N) | 순차 탐색(O(N)) | 이진 탐색(O(log N)) |
|---|---|---|
10^3 (1,000) | 최대 1,000번 | 약 10번 |
10^6 (1,000,000) | 최대 1,000,000번 | 약 20번 |
10^9 (1,000,000,000) | 최대 1,000,000,000번 | 약 30번 |
✅ 데이터가 많아질수록 이진 탐색이 훨씬 빠름!
4. 이진 탐색의 구현 방법
이진 탐색은 반복문(while)을 사용한 방법과 재귀(recursion)를 사용한 방법이 있다.
1) 반복문(while)을 사용하는 이진 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 # 값을 찾지 못한 경우
실행 예시
1
2
3
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(arr, target)) # 출력: 3 (인덱스)
7은arr[3]에 위치 →3출력- 정렬된 배열에서
O(log N)의 시간으로 빠르게 탐색!
2) 재귀를 사용하는 이진 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1 # 찾지 못한 경우
mid = (left + right) // 2 # 중간값 설정
if arr[mid] == target: # 정답을 찾음
return mid
elif arr[mid] < target: # 오른쪽 탐색
return binary_search_recursive(arr, target, mid + 1, right)
else: # 왼쪽 탐색
return binary_search_recursive(arr, target, left, mid - 1)
# 실행 예시
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search_recursive(arr, target, 0, len(arr) - 1)) # 출력: 3
- 반복문 없이 “재귀 함수”를 사용하여 같은 방식으로 탐색
- 하지만, 재귀 함수는 호출 스택이 추가되므로
while반복문보다 메모리 효율이 낮음 - 반복문 방식이 일반적으로 더 선호됨!
5. 이진 탐색이 사용되는 문제 유형
- 숫자 찾기 문제
- 정렬된 배열에서 특정 숫자가 있는지 확인 (
이진 탐색 기본 문제)
- 정렬된 배열에서 특정 숫자가 있는지 확인 (
- 최적화 문제
- “최소 또는 최대값을 찾는 문제” (
이진 탐색을 활용한 최적화)
- “최소 또는 최대값을 찾는 문제” (
- 결정 문제 (Yes or No)
- “이 값이 가능한가?”를 판단하는 문제
- 예제: 특정 거리(
mid)를 유지하면서 바위를n개 제거할 수 있는가?
6. “이진 탐색”을 떠올려야 하는 문제 유형
| 문제 유형 | 설명 | 예시 |
|---|---|---|
| 정렬된 배열에서 값 찾기 | 데이터가 정렬된 상태에서 특정 값 찾기 | 정렬된 배열에서 특정 숫자 찾기 |
| 최적의 값 찾기 | “최소/최대” 값을 찾아야 하는 경우 | 바위를 n개 제거해서 최적의 거리 찾기 |
| 결정 문제(가능 여부 판단) | “이 값이 가능한가?” 판단 | 특정 값으로 조건을 만족할 수 있는지 |
7. 이진 탐색과 “완전 탐색” 비교
| 방법 | 설명 | 시간 복잡도 | 최대 10억 개의 데이터에서 실행 가능? |
|---|---|---|---|
| 완전 탐색(Brute Force) | 하나씩 비교 | O(N) | ❌ (10억 번 반복 → 불가능) |
| 이진 탐색(Binary Search) | O(log N)으로 빠르게 탐색 | O(log N) | ✅ (30 번 이내에 탐색 가능) |
결론: “탐색할 범위가 크다면, 이진 탐색을 사용하자!”
📌 정리
- 이진 탐색은 “정렬된 데이터에서 특정 값을 빠르게 찾는 방법”
- 탐색 범위를 절반씩 줄여
O(log N)의 빠른 속도를 제공 - “최적의 값 찾기”와 “결정 문제” 유형에서 유용
- 탐색 범위가
10억이상이면, 반드시 이진 탐색을 고려해야 함!
코딩테스트 문제에서 “이진 탐색”을 사용해야 한다는 점을 어떻게 추측할 수 있을까?
문제 : 프로그래머스-징검다리
문제를 처음 봤을 때, 이진 탐색(Binary Search) 이 필요하다는 사실을 바로 알 수는 없다. 하지만, 몇 가지 중요한 힌트를 통해 이진 탐색이 적합한 알고리즘이라는 점을 추측할 수 있다.
1. 문제에서 “최적화된 값”을 찾아야 함
문제에서 우리가 찾아야 하는 것은 “최소 거리의 최댓값” 이다. 즉, 정확한 값이 아니라, 특정 조건을 만족하는 최적의 값을 찾아야 한다.
- 예시:
- 바위를
n개 제거했을 때, - 바위들 사이의 거리 중 가장 작은 값이 최대가 되도록 해야 한다.
- 바위를
이런 유형의 문제는 단순히 정렬이나 반복문으로 해결하기 어렵고, 탐색(Searching)이 필요하다는 것을 암시
2. “최적의 값”을 찾는 과정에서 탐색 범위가 크다
제한 조건을 보면,
distance(출발점에서 도착점까지 거리) → 최대1,000,000,000(10억)rocks(바위 개수) → 최대50,000개n(제거할 바위 개수) → 최대50,000개
이제 가능한 거리의 범위를 생각해보자.
- 최소 거리:
1(바위가 가장 가까이 붙어 있을 때) - 최대 거리:
distance(바위를 모두 제거했을 때) - 즉, 거리의 범위는 최대
1,000,000,000(10억)
“가능한 거리”를 전부 탐색하면 최대 10억 개를 확인해야 하므로, 단순한 반복문(O(N))으로는 시간이 너무 오래 걸린다.
즉, 빠르게 정답을 찾기 위해 “이진 탐색”을 적용
3. 이진 탐색이 필요한 이유: “결과가 정렬된 형태”
이진 탐색(Binary Search)은 “정렬된 범위에서 최적의 값을 찾을 때” 가장 적합한 방법이다. 이 문제에서는 바위를 정렬하면, 바위 사이의 거리를 구하는 것이 순차적인(정렬된) 문제로 변환된다. 즉, 바위 사이의 거리를 이진 탐색을 이용해 탐색할 수 있다.
예제 예시
예제 입력: rocks = [2, 14, 11, 21, 17]
- 바위를 정렬하면
[2, 11, 14, 17, 21, 25]
이제, 바위 사이의 거리는 [2, 9, 3, 4, 4]와 같이 정렬된 상태에서 다루게 된다. 💡 “정렬된 상태에서 특정 값을 찾는다” → 이진 탐색 가능!
4. “결과를 예측하고 조정할 수 있는 값”이 있다
이진 탐색을 적용하려면 “이 값이 가능할까?” 라고 판단할 수 있는 기준이 있어야 한다. 이 문제에서, 바위 사이의 거리를 특정 값(mid)로 유지할 수 있는지 판단할 수 있다.
mid값(최소 거리)을 설정하고,- 바위들을 하나씩 확인하면서 mid 값을 유지할 수 없으면 바위를 제거
- 만약
n개 이하로 제거하면 mid 값을 늘려 더 큰 최소 거리를 탐색 - 반대로,
n개보다 많이 제거해야 한다면 mid 값을 줄여야 함
즉, “mid 값이 가능할지”를 판단할 기준이 존재하기 때문에, 이진 탐색이 적합.
“이진 탐색이 적합한 이유”
| 조건 | 설명 | 이진 탐색 사용 가능 여부 |
|---|---|---|
| 1. 최적의 값을 찾아야 함 | “최소 거리 중 최댓값”을 찾아야 함 | ✅ |
| 2. 탐색 범위가 매우 큼 | 거리 범위가 최대 10억 → 선형 탐색 불가 | ✅ |
| 3. 정렬된 상태에서 찾을 수 있음 | 바위를 정렬하면 거리 계산이 쉬움 | ✅ |
| 4. “이 값이 가능한가?”를 판단할 기준이 있음 | 특정 거리(mid) 유지 가능 여부를 판단할 수 있음 | ✅ |
✅ 마무리: 문제에서 “이진 탐색”을 떠올리는 과정
- 문제에서 “최적의 값”을 찾아야 한다 → 단순한 반복문으로 해결 어려움
- 탐색 범위가 크다 (
10억이상) →O(N^2)이나O(N)으로는 불가능 - 정렬 후 순차적으로 탐색 가능 → 이진 탐색을 적용할 수 있음
- “이 값(mid)이 가능할까?”를 판별할 수 있음 → 이진 탐색을 적용할 수 있음
이러한 요소를 조합했을 때, “이진 탐색이 필요하겠다!” 라는 결론을 내릴 수 있다