#이분탐색

정답 가능 여부가 단조롭게 변하는 문제에서 탐색 범위를 절반씩 줄이는 이분 탐색 풀이를 다룬다. 현재 5개의 풀이가 있다.

LeetCode2026년 9월 10일

LeetCode 704 Binary Search 풀이: 정렬 배열 이분 탐색

LeetCode 704 Binary Search를 정렬된 배열에서 이분 탐색으로 푼다. 닫힌 구간의 불변식과 경계 갱신을 확인하고, O(log n) 시간과 O(1) 공간으로 목표값의 인덱스를 찾는다.

LeetCode2026년 9월 20일

LeetCode 875 Koko Eating Bananas 풀이: 가능 여부 판정 이분 탐색

LeetCode 875 Koko Eating Bananas에서 주어진 속도로 제한 시간 안에 먹을 수 있는지 판정한다. 이분 탐색으로 필요한 최소 시간당 섭취량을 찾는다.

LeetCode2026년 9월 18일

LeetCode 74 Search a 2D Matrix 풀이: 2차원 배열을 평탄화한 이분 탐색

LeetCode 74 Search a 2D Matrix에서 행렬을 하나의 정렬된 배열처럼 보고 이분 탐색한다. 가상 1차원 인덱스를 행·열 좌표로 바꿔 O(log(mn)) 시간과 O(1) 공간에 target을 찾는다.

LeetCode2026년 10월 10일

LeetCode 981 Time Based Key-Value Store 풀이: 키별 시간 배열과 이분 탐색

LeetCode 981 Time Based Key-Value Store에서 키별 timestamp 이력을 저장하고, 조회 시각 이하의 가장 최근 기록을 이분 탐색으로 찾는다. set은 평균 O(1), 키별 기록이 k개일 때 get은 O(log k)다.

프로그래머스2026년 9월 5일

프로그래머스 퍼즐 게임 챌린지 풀이: 이분 탐색으로 최소 숙련도 찾기

프로그래머스 퍼즐 게임 챌린지에서 숙련도별 총 소요 시간을 판정하고 이분 탐색으로 최소 숙련도를 찾는다. 실패 횟수에 따른 시간 계산과 단조 조건을 설명한다.

이분 탐색 학습 가이드

필요한 주제만 펼쳐서 탐색 구간과 경계를 안전하게 줄이는 방법을 익힌다.

이분 탐색 기본 개념

이분 탐색은 정렬된 데이터나 답의 가능 여부가 단조롭게 변하는 공간에서 중간을 확인하고, 정답이 있을 수 없는 절반을 버리는 알고리즘이다.

중간값과 비교한 뒤 정답이 없는 절반을 버리면 탐색 범위가 빠르게 줄어든다.

탐색 구간: 아직 정답 후보로 남아 있는 왼쪽과 오른쪽 경계
중간값: 현재 구간을 나누기 위해 확인하는 위치
단조성: 한쪽이 불가능하면 그 바깥쪽도 모두 불가능하다는 성질
종료: 값을 찾거나 후보 구간이 비었을 때 종료

정렬된 배열에서 값을 찾는 문제뿐 아니라, 특정 능력으로 가능한지 판정하는 문제의 정답 범위에도 적용할 수 있다.

정답 판정 함수로 탐색하기

정답 자체를 직접 찾기 어렵다면 후보 값 `x`를 정하고 “`x`로 조건을 만족할 수 있는가?”를 판정한다. 이 결과가 `false`에서 `true`로 한 번만 바뀌면 경계에 이분 탐색을 적용할 수 있다.

가능 여부가 false에서 true로 한 번만 바뀌면 첫 true 또는 마지막 false를 찾을 수 있다.

최솟값 찾기: 가능한 후보 중 첫 번째 `true` 찾기
최댓값 찾기: 가능한 후보 중 마지막 `true` 찾기
판정 함수: 후보 하나를 검증하는 데 필요한 계산

판정 함수가 매번 `O(n)`이라면 전체 시간 복잡도는 정답 범위 크기를 `R`이라 할 때 `O(n log R)`가 된다.

탐색 경계와 갱신 규칙

구간을 `[left, right]`처럼 닫힌 범위로 정했다면 모든 갱신은 이 정의를 끝까지 유지해야 한다. `mid`를 제외할 수 있는지, 정답 후보로 남겨야 하는지를 먼저 결정한다.

현재 판정 결과에 따라 중간값을 버릴지 정답 후보로 남길지를 구분해야 한다.

left, right = start, end
while left <= right:
    mid = (left + right) // 2
    if is_valid(mid):
        right = mid - 1
    else:
        left = mid + 1

위 코드는 가능한 최솟값을 찾는 대표적인 형태다. `is_valid(mid)`가 참이어도 더 작은 정답이 있을 수 있으므로 `mid`를 바로 버리지 않는다.

문제 조건별 이분 탐색 선택

문제 조건	탐색 대상	핵심 판정
정렬된 배열에서 값 찾기	배열 인덱스	중간값과 target 비교
처음 나타나는 위치 찾기	인덱스 경계	같아도 왼쪽 구간 유지
최소 가능한 용량·시간 찾기	정답 후보 숫자	해당 값으로 조건 만족 가능 여부
최대 가능한 점수·거리 찾기	정답 후보 숫자	해당 값 이상을 만들 수 있는지
회전된 정렬 배열 탐색	배열 구간	정렬된 절반 식별

자주 하는 실수

탐색 구간이 닫힌 범위인지 반열린 범위인지 섞어 쓰는 경우
`left = mid` 또는 `right = mid`로 갱신해 구간이 줄지 않는 경우
첫 번째 true와 마지막 true 중 어떤 경계를 찾는지 구분하지 않는 경우
판정 함수의 결과가 단조롭지 않은데 이분 탐색을 적용하는 경우
정답 후보가 될 수 있는 `mid`를 너무 일찍 버리는 경우

전체 문제 풀이 보기