[알고리즘] 이분탐색 (Binary Search)이란? (백준 10816 , 1654, 2805)

📌 핵심 요약

• 이분탐색 — 정렬된 배열에서 탐색 범위를 절반씩 줄여 O(log N)에 값을 찾는다
• 파라메트릭 서치 — "이 값이 정답일 수 있을까?"를 매번 검증하며 정답 후보를 좁혀간다
• 문제풀이 — 백준 문제 10816, 1654, 2805를 풀이하며 이분탐색을 활용해본다.

 

목차

 

1 이분탐색 기본 개념

정렬된 배열에서 특정 값을 찾을 때, 처음부터 끝까지 하나씩 확인하면 O(N)이 걸린다. 이분탐색은 탐색 범위를 매번 절반으로 줄여 O(log N)에 찾아낸다.

ℹ️

전제 조건

이분탐색은 반드시 정렬된 배열에서만 사용할 수 있다. 정렬되지 않은 배열에 적용하면 틀린 답이 나온다.

기본 구조

 

Java — 기본 이분탐색

static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 오버플로 방지

        if (arr[mid] == target)      return mid;
        else if (arr[mid] < target)  lo = mid + 1;
        else                          hi = mid - 1;
    }
    return -1;
}

lower bound / upper bound

단순히 값을 찾는 게 아니라 "처음 등장 위치"나 "마지막 등장 위치+1"이 필요할 때 사용한다.

 

Java — lower bound / upper bound

// lower bound: arr[mid] >= target 을 처음 만족하는 인덱스
static int lowerBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid;
    }
    return lo;
}

// upper bound: arr[mid] > target 을 처음 만족하는 인덱스
static int upperBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;  // <= 딱 한 글자 차이
        else                    hi = mid;
    }
    return lo;
}

💡

lower vs upper 기억법

lower bound — target 미만이면 오른쪽 (<)
upper bound — target 이하이면 오른쪽 (<=)
else hi = mid는 두 함수가 완전히 동일하다.

2 백준 10816 — 숫자 카드 2

백준 #10816

숫자 카드 2

N, M ≤ 500,000 · 시간제한 2초

난이도: Silver IV

N개의 숫자 카드 중 M개의 쿼리 숫자가 각각 몇 번 등장하는지 출력한다.

핵심 아이디어

배열을 정렬하면 같은 숫자들이 연속된 구간으로 모인다. upper bound - lower bound로 구간의 길이 = 등장 횟수를 구한다.

정렬 후: -10 -10  2  3  3  6  7  10  10  10
인덱스:    0   1  2  3  4  5  6   7   8   9

target=10: upper(10) - lower(10) = 10 - 7 = 3

풀이 과정

1. N개 카드를 배열에 저장하고 오름차순 정렬한다
2. M개 쿼리마다 lower bound와 upper bound를 각각 구한다
3. upper - lower가 해당 숫자의 등장 횟수다

 

Java — 백준 10816

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine().trim());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine().trim());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            int count = upperBound(arr, target) - lowerBound(arr, target);
            sb.append(count);
            if (i < m - 1) sb.append(' ');
        }
        System.out.println(sb);
    }

    static int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < target) lo = mid + 1;
            else                   hi = mid;
        }
        return lo;
    }

    static int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] <= target) lo = mid + 1;
            else                    hi = mid;
        }
        return lo;
    }
}

3 백준 1654 — 랜선 자르기

백준 #1654

랜선 자르기

K ≤ 10,000 · N ≤ 10,000 · 시간제한 2초

난이도: Silver III

K개의 랜선을 잘라 N개를 만들 때, 만들 수 있는 랜선의 최대 길이를 구한다.

핵심 아이디어 — 파라메트릭 서치

배열에서 값을 찾는 게 아니라 "길이 X로 자르면 N개를 만들 수 있을까?"를 검증하며 최대 X를 찾는다. X가 커질수록 만들 수 있는 개수가 줄어드는 단조 구조이므로 이분탐색이 가능하다.

풀이 과정

1. 탐색 범위: lo=1, hi=최대 랜선 길이+1
2. mid 길이로 잘랐을 때 총 개수 = 각 랜선에서 cable / mid의 합
3. 개수가 N 이상이면 answer = mid로 저장하고 더 긴 길이도 시도
4. 개수가 N 미만이면 길이를 줄여야 하므로 hi = mid - 1

⚠️

자료형 주의

랜선 길이 최대 2³¹-1, 개수 최대 10,000개 → count가 int 범위를 넘을 수 있다. lo, hi, mid, count 모두 long으로 선언해야 한다.

 

Java — 백준 1654

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        long[] arr = new long[k];
        for (int i = 0; i < k; i++) {
            arr[i] = Long.parseLong(br.readLine().trim());
        }

        Arrays.sort(arr);

        long lo = 1, hi = arr[arr.length - 1];
        long answer = 0;

        while (lo <= hi) {
            long mid = (lo + hi) / 2;

            long count = 0;
            for (long cable : arr) count += cable / mid;

            if (count >= n) {
                answer = mid;   // 정답 후보 저장
                lo = mid + 1;  // 더 긴 길이도 가능한지 확인
            } else {
                hi = mid - 1;  // 너무 길게 자름
            }
        }
        System.out.println(answer);
    }
}

4 백준 2805 — 나무 자르기

백준 #2805

나무 자르기

N ≤ 1,000,000 · 시간제한 1초

난이도: Silver II

절단기 높이를 H로 설정하면 H보다 높은 나무는 나무 높이 - H만큼 잘린다. 잘린 나무의 합이 M 이상이 되는 최대 H를 구한다.

1654번과의 비교

구조는 1654번과 동일한 파라메트릭 서치다. mid의 의미만 다르다.

문제	mid의 의미	count 계산
1654 랜선	랜선 길이	cable / mid 합산
2805 나무	절단기 높이	tree - mid 합산 (tree > mid인 경우)

풀이 과정

1. 탐색 범위: lo=1, hi=최대 나무 높이
2. 높이 mid로 잘랐을 때 얻는 목재 = 각 나무에서 Math.max(tree - mid, 0)의 합
3. 목재 합이 M 이상이면 answer = mid 저장 후 더 높은 절단 시도
4. 목재 합이 M 미만이면 더 낮게 잘라야 하므로 hi = mid - 1

⚠️

자료형 주의

나무 높이 최대 1,000,000,000 × N 최대 1,000,000 → count 합산이 int 범위를 훨씬 넘는다. long으로 선언 필수.

 

Java — 백준 2805

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        long[] arr = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Long.parseLong(st.nextToken());

        Arrays.sort(arr);

        long lo = 1, hi = arr[arr.length - 1];
        long answer = 0;

        while (lo <= hi) {
            long mid = (lo + hi) / 2;

            long count = 0;
            for (long tree : arr) {
                if (tree > mid) count += tree - mid;
            }

            if (count >= m) {
                answer = mid;   // 정답 후보 저장
                lo = mid + 1;  // 더 높이 잘라도 되는지 확인
            } else {
                hi = mid - 1;  // 너무 높게 자름
            }
        }
        System.out.println(answer);
    }
}

💡

파라메트릭 서치 공통 패턴

세 문제(1654, 2805, 2110) 모두 동일한 틀을 사용한다.
answer = mid 저장 → 조건 만족 시 더 좋은 방향으로 탐색 → 조건 불만족 시 반대 방향으로 탐색

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.