이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리
이 글의 핵심
이진 탐색에 대한 실전 가이드입니다. O(log n) 탐색 알고리즘 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”정렬된 배열에서 찾기 = 이진 탐색”
이진 탐색은 정렬된 배열에서 O(log n)으로 값을 찾는 알고리즘입니다. 선형 탐색 O(n)보다 훨씬 빠릅니다.
사전 지식 (초보자를 위한 기초)
1. 배열이란?
배열은 여러 개의 값을 순서대로 저장하는 자료구조입니다. 책장에 책을 순서대로 꽂아두는 것과 같습니다.
# 배열 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]
# 0 1 2 3 4 5 6 7 (인덱스 = 위치)
# 인덱스로 값 접근
print(arr[0]) # 1 (첫 번째 값)
print(arr[3]) # 7 (네 번째 값)2. 정렬된 배열이란?
정렬된 배열은 값이 작은 것부터 큰 순서로 나열된 배열입니다.
# 정렬된 배열
sorted_arr = [1, 3, 5, 7, 9] # ✅ 작은 것 → 큰 것
# 정렬되지 않은 배열
unsorted_arr = [5, 1, 9, 3, 7] # ❌ 순서가 뒤죽박죽왜 정렬이 중요한가?
- 이진 탐색은 정렬된 배열에서만 작동합니다
- 정렬되지 않은 배열은 먼저 정렬해야 합니다
3. 시간 복잡도란?
시간 복잡도는 알고리즘이 얼마나 빠른지 나타내는 지표입니다.
# O(n) - 선형 탐색 (느림)
# 배열의 모든 요소를 하나씩 확인
def linear_search(arr, target):
for i in range(len(arr)): # n번 반복
if arr[i] == target:
return i
return -1
# 예시: 배열 크기가 1000개면 최악의 경우 1000번 확인
# O(log n) - 이진 탐색 (빠름)
# 배열을 절반씩 줄여가며 확인
# 예시: 배열 크기가 1000개면 최악의 경우 10번만 확인
# 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1비교:
| 배열 크기 | O(n) 선형 탐색 | O(log n) 이진 탐색 |
|---|---|---|
| 10개 | 10번 | 4번 |
| 100개 | 100번 | 7번 |
| 1,000개 | 1,000번 | 10번 |
| 1,000,000개 | 1,000,000번 | 20번 |
이진 탐색이 훨씬 빠릅니다!
4. 이진 탐색의 핵심 아이디어
“사전에서 단어 찾기”를 생각해보세요:
사전에서 "사과" 찾기:
1. 사전을 가운데 펼침 → "마" 나옴
2. "사"는 "마"보다 뒤에 있음 → 앞쪽 절반은 버림
3. 남은 절반의 가운데 펼침 → "자" 나옴
4. "사"는 "자"보다 앞에 있음 → 뒤쪽 절반은 버림
5. 남은 절반의 가운데 펼침 → "사" 찾음!
매번 절반씩 버리니까 빠르게 찾을 수 있습니다!이진 탐색도 똑같은 원리입니다:
- 배열의 가운데 값을 확인
- 찾는 값이 가운데보다 작으면 → 왼쪽 절반만 탐색
- 찾는 값이 가운데보다 크면 → 오른쪽 절반만 탐색
- 반복하면 빠르게 찾을 수 있음
1. 이진 탐색 기본
알고리즘
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]에서 7 찾기
1. 중간값 확인: arr[4] = 9 > 7 → 왼쪽 절반
2. 중간값 확인: arr[1] = 3 < 7 → 오른쪽 절반
3. 중간값 확인: arr[2] = 5 < 7 → 오른쪽 절반
4. 중간값 확인: arr[3] = 7 = 7 → 찾음!Python 구현
이진 탐색은 정렬된 배열을 절반씩 잘라 탐색 범위를 줄입니다. 사전에서 단어를 찾을 때 가운데를 펼쳐 보고, 찾는 글자가 앞쪽인지 뒤쪽인지로 절반을 버리는 것과 같은 방식입니다.
def binary_search(arr, target):
# 탐색 범위: [left, right]
left, right = 0, len(arr) - 1
# left가 right를 넘어가면 못 찾은 것
while left <= right:
# 중간 인덱스 계산
mid = (left + right) // 2
# 주의: (left + right) / 2는 오버플로우 가능 (C/C++)
# Python은 정수 오버플로우 없음
# 더 안전한 방법: mid = left + (right - left) // 2
if arr[mid] == target:
# 찾았음!
return mid
elif arr[mid] < target:
# 중간값이 target보다 작음
# target은 오른쪽 절반에 있음
left = mid + 1 # 왼쪽 절반 버림
else:
# 중간값이 target보다 큼
# target은 왼쪽 절반에 있음
right = mid - 1 # 오른쪽 절반 버림
# 못 찾음
return -1
# 테스트
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7)) # 3 (인덱스 3에 7이 있음)
print(binary_search(arr, 10)) # -1 (10은 배열에 없음)
# 탐색 과정 (target=7):
# arr = [1, 3, 5, 7, 9, 11, 13, 15]
# 0 1 2 3 4 5 6 7 (인덱스)
#
# 1단계: left=0, right=7
# mid = (0+7)//2 = 3
# arr[3] = 7 == 7 → 찾음!
# return 3
#
# 탐색 과정 (target=11):
# 1단계: left=0, right=7
# mid = 3, arr[3] = 7 < 11
# left = 4 (오른쪽 절반으로)
#
# 2단계: left=4, right=7
# mid = (4+7)//2 = 5
# arr[5] = 11 == 11 → 찾음!
# return 5
#
# 시간복잡도: O(log n)
# 매번 탐색 범위가 절반으로 줄어듦
# n=1000 → 최대 10번 비교
# n=1000000 → 최대 20번 비교선형 탐색 vs 이진 탐색:
# 선형 탐색: O(n)
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 최악의 경우: 모든 요소 확인 (n번)
# 이진 탐색: O(log n)
# 최악의 경우: log₂(n)번만 확인
#
# 성능 비교 (n=1000000):
# 선형: 1000000번 비교 (최악)
# 이진: 20번 비교 (최악)
# → 50000배 빠름!재귀 구현
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]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1)) # 32. Lower Bound & Upper Bound
Lower Bound
x 이상인 첫 번째 위치를 찾습니다:
def lower_bound(arr, x):
# 탐색 범위: [left, right)
# right = len(arr)로 설정 (배열 끝 다음)
left, right = 0, len(arr)
# left == right가 되면 종료
while left < right:
mid = (left + right) // 2
# arr[mid] < x: mid는 답이 될 수 없음
if arr[mid] < x:
# x보다 작으면 오른쪽으로
left = mid + 1
else:
# arr[mid] >= x: mid가 답일 수 있음
# x 이상이면 왼쪽으로 (더 작은 인덱스 찾기)
right = mid
# left가 x 이상인 첫 위치
return left
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
# 0 1 2 3 4 5 6 (인덱스)
print(lower_bound(arr, 2)) # 1 (첫 번째 2의 위치)
# 2 이상인 첫 위치 = 인덱스 1
print(lower_bound(arr, 3)) # 4 (3의 위치)
# 3 이상인 첫 위치 = 인덱스 4
print(lower_bound(arr, 0)) # 0 (배열 시작)
# 0 이상인 첫 위치 = 인덱스 0
print(lower_bound(arr, 10)) # 7 (배열 끝)
# 10 이상인 값이 없음 → len(arr) 반환
# 탐색 과정 (x=2):
# arr = [1, 2, 2, 2, 3, 4, 5]
#
# 1단계: left=0, right=7
# mid = 3, arr[3] = 2 >= 2
# right = 3 (mid가 답일 수 있음)
#
# 2단계: left=0, right=3
# mid = 1, arr[1] = 2 >= 2
# right = 1
#
# 3단계: left=0, right=1
# mid = 0, arr[0] = 1 < 2
# left = 1
#
# 4단계: left=1, right=1
# 종료 → return 1Lower Bound 활용:
# 1. 중복된 값의 첫 위치 찾기
arr = [1, 2, 2, 2, 3, 4, 5]
first_2 = lower_bound(arr, 2) # 1
# 2. 삽입 위치 찾기 (정렬 유지)
arr = [1, 3, 5, 7, 9]
pos = lower_bound(arr, 6) # 3
arr.insert(pos, 6) # [1, 3, 5, 6, 7, 9]
# 3. 범위 쿼리 (x 이상인 개수)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_gte_5 = len(arr) - lower_bound(arr, 5) # 5
# 5 이상: [5, 6, 7, 8, 9] → 5개Upper Bound
x 초과인 첫 번째 위치를 찾습니다:
def upper_bound(arr, x):
# 탐색 범위: [left, right)
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
# arr[mid] <= x: mid는 답이 될 수 없음
if arr[mid] <= x:
# x 이하면 오른쪽으로
left = mid + 1
else:
# arr[mid] > x: mid가 답일 수 있음
# x 초과면 왼쪽으로 (더 작은 인덱스 찾기)
right = mid
# left가 x 초과인 첫 위치
return left
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
# 0 1 2 3 4 5 6 (인덱스)
print(upper_bound(arr, 2)) # 4 (2 다음 위치)
# 2 초과인 첫 위치 = 인덱스 4 (값 3)
print(upper_bound(arr, 3)) # 5 (3 다음 위치)
# 3 초과인 첫 위치 = 인덱스 5 (값 4)
print(upper_bound(arr, 5)) # 7 (배열 끝)
# 5 초과인 값이 없음 → len(arr) 반환
# Lower Bound vs Upper Bound:
# arr = [1, 2, 2, 2, 3, 4, 5]
# 0 1 2 3 4 5 6
#
# x=2:
# lower_bound(arr, 2) = 1 (2 이상인 첫 위치)
# upper_bound(arr, 2) = 4 (2 초과인 첫 위치)
#
# 차이: upper_bound - lower_bound = 중복 개수
# 4 - 1 = 3 (2가 3개)Upper Bound 활용:
# 1. 중복된 값의 마지막 다음 위치
arr = [1, 2, 2, 2, 3, 4, 5]
last_2_next = upper_bound(arr, 2) # 4
# 2의 마지막 인덱스 = last_2_next - 1 = 3
# 2. 중복 개수 세기
def count_occurrences(arr, x):
return upper_bound(arr, x) - lower_bound(arr, x)
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2)) # 3
# upper_bound(2) - lower_bound(2) = 4 - 1 = 3
# 3. 범위 쿼리 (x 이하인 개수)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_lte_5 = upper_bound(arr, 5) # 5
# 5 이하: [1, 2, 3, 4, 5] → 5개
# 4. 삽입 위치 (중복 허용, 뒤에 삽입)
arr = [1, 2, 2, 2, 3]
pos = upper_bound(arr, 2) # 4
arr.insert(pos, 2) # [1, 2, 2, 2, 2, 3]C++ STL 함수:
#include <algorithm>
#include <vector>
std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
// Lower Bound: x 이상인 첫 위치
auto it1 = std::lower_bound(arr.begin(), arr.end(), 2);
// it1 = arr.begin() + 1
// Upper Bound: x 초과인 첫 위치
auto it2 = std::upper_bound(arr.begin(), arr.end(), 2);
// it2 = arr.begin() + 4
// 개수 세기
int count = it2 - it1; // 3개수 세기
def count_occurrences(arr, x):
"""
정렬된 배열에서 x의 개수 (O(log n))
"""
return upper_bound(arr, x) - lower_bound(arr, x)
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2)) # 33. 파라메트릭 서치
개념
최적화 문제 → 결정 문제로 변환:
"최소 몇 개?" → "k개로 가능한가?" (이진 탐색)예제: 나무 자르기
def cut_trees(trees, h):
"""
높이 h로 잘랐을 때 얻는 나무 길이
"""
return sum(max(0, tree - h) for tree in trees)
def find_max_height(trees, target):
"""
target 길이 이상을 얻을 수 있는 최대 높이
"""
left, right = 0, max(trees)
result = 0
while left <= right:
mid = (left + right) // 2
if cut_trees(trees, mid) >= target:
result = mid # 가능 → 더 높게
left = mid + 1
else:
right = mid - 1 # 불가능 → 더 낮게
return result
# 테스트
trees = [20, 15, 10, 17]
target = 7
print(find_max_height(trees, target)) # 15
# 높이 15로 자르면: 5 + 0 + 0 + 2 = 7실전 팁
코딩 테스트 팁
# ✅ Python 내장 함수 활용
import bisect
arr = [1, 2, 3, 5, 6, 7]
idx = bisect.bisect_left(arr, 4) # Lower Bound
print(idx) # 3
bisect.insort(arr, 4) # 정렬 유지하며 삽입
print(arr) # [1, 2, 3, 4, 5, 6, 7]주의사항
# ❌ 오버플로우 주의 (C++)
# mid = (left + right) / 2; // left + right 오버플로우!
# ✅ 안전한 방법
# mid = left + (right - left) / 2;
# Python은 오버플로우 걱정 없음
mid = (left + right) // 2정리
핵심 요약
- 이진 탐색: 정렬된 배열에서 O(log n) 탐색
- Lower Bound: x 이상인 첫 위치
- Upper Bound: x 초과인 첫 위치
- 파라메트릭 서치: 최적화 → 결정 문제
추천 문제
백준:
프로그래머스:
LeetCode:
관련 글
- 정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐