이진 탐색은 언제 쓰나요?

정렬된 배열에서 특정 값을 찾을 때 사용합니다. O(n) → O(log n)으로 최적화.

Lower Bound와 Upper Bound 차이는?

Lower Bound는 x 이상인 첫 위치, Upper Bound는 x 초과인 첫 위치입니다.

파라메트릭 서치는 뭔가요?

최적화 문제를 결정 문제로 바꿔서 이진 탐색으로 푸는 기법입니다.

이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리

2026년 3월 28일 · 16분 읽기 · 수정 2026년 4월 7일 중급 튜토리얼

이 글의 핵심

이진 탐색: O(log n) 탐색 알고리즘 이진 탐색 기본·Lower Bound & Upper Bound.

시리즈 안내

#09 | 📋 전체 목차 | 이전: #08 정렬 문제 · 다음: #10 BFS와 DFS

들어가며

”정렬된 배열에서 찾기 = 이진 탐색”

이진 탐색은 정렬된 배열에서 O(log n)으로 값을 찾는 알고리즘입니다. 선형 탐색 O(n)보다 훨씬 빠릅니다.

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

사전 지식 (초보자를 위한 기초)

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))  # 3

2. 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 1

Lower 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))  # 3

3. 파라메트릭 서치

개념

최적화 문제 → 결정 문제로 변환:

"최소 몇 개?" → "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 초과인 첫 위치
파라메트릭 서치: 최적화 → 결정 문제

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 이진 탐색: O(log n) 탐색 알고리즘 완벽 정리. 이진 탐색 기본·Lower Bound & Upper Bound로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. 알고리즘·이진탐색·Binary Searc… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

알고리즘, 이진탐색, Binary Search, 코딩테스트, 정렬 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.