[알고리즘] 이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)

이분 탐색(Binary Search)과 매개변수 탐색(Parametric Search)에 대해 공부 후 정리하였습니다.

1. 이분 탐색 (Binary Search)

추가할 내용

• 주의 사항 : 무한루프 주의 - start와 end가 1차이날 때 주의깊게 확인 (start+end+1)/2
• 정렬되어야 함
• 응용 문제 : 해당 타겟이 몇 개 있는지 찾기 (왼쪽과 오른쪽 위치를 찾아서 계산)
  • upper/lower bound
• 응용 문제 : 뭔가를 2개 묶은 후, 한쪽의 값을 이분 탐색으로 찾기 -> 시간 단축

개념

정렬된 데이터에서 원하는 값을 빠르게 찾는 탐색 알고리즘
“중간값(mid)”과 비교해 탐색 범위를 절반씩 줄여가는 방식

특징

• 데이터가 정렬되어 있어야 사용 가능 (오름차순 또는 내림차순)
• 탐색 범위를 절반씩 줄이므로 효율적
• 정확히 일치하는 값 뿐만 아니라, 특정 조건을 만족하는 첫 번째/마지막 인덱스 탐색도 가능

시간 복잡도

정렬된 경우 : O(log N)

• 매 단계마다 검색 범위가 절반으로 줄어듦
• N이 1,000,000 → 약 20번 비교

정렬되지 않은 경우 : O(NlogN + logN)

기본 코드

import java.util.*;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;

        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println(target + " 찾음 (인덱스: " + index + ")");
        } else {
            System.out.println(target + " 없음");
        }
    }

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

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반으로 이동
            } else {
                right = mid - 1; // 왼쪽 절반으로 이동
            }
        }
        return -1; // 못 찾음
    }
}

Arrays.binarySearch() 정리

2. 매개변수 탐색 (Parametric Search)

개념

이분 탐색을 “정답”이 아닌 “조건”에 적용하는 기법
“가능하다 / 불가능하다”로 판별하며, 답이 될 수 있는 범위에서 조건을 만족하는 최적값을 찾는 방법

= 조건을 만족하는 최소/최대값을 구하는 문제인 최적화 문제를 결정 문제로 변환해 이분탐색을 수행하는 것

특징

• “조건을 만족하는 최대/최소 값”을 구할 때 사용
• 정답이 수치형 범위(1 ~ 10^9 등)일 때 특히 유용
• 조건 검증 함수(isPossible)의 시간 복잡도가 O(N) → 전체는 O(N log MaxValue)

방법

1. 결정 문제로 변환 가능한 지 확인하기

   • (최적화 문제) N개를 만들 수 있는 랜선의 최대 길이
   • (결정 문제) 랜선 길이가 x일 때, 랜선이 N개 이상인가 아닌가

2. 감소/증가 함수인지 확인하기 (일정하지 않으면 이분 탐색 불가능)

📌 구조

• 답의 범위를 설정
• 중간값 mid를 답이라고 가정
• mid가 조건을 만족하는지 판별 (O(N) 검증 함수)
• 조건 만족 여부에 따라 탐색 범위를 줄임
  • 조건 만족 → 더 좋은 해(작거나 큰 값)를 찾기 위해 범위 좁힘
  • 조건 불만족 → 반대쪽으로 이동

예시 문제 : 나무 자르기 문제 (백준 2805)

N개의 나무 중 H 높이 이상만 잘라서 가져가는데, 가져가는 나무의 합이 M 이상이 되도록 하는 최대 절단기 높이 찾기

import java.util.*;

public class TreeCutting {
    static int[] trees;
    static int N, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        trees = new int[N];
        int maxTree = 0;

        for (int i = 0; i < N; i++) {
            trees[i] = sc.nextInt();
            maxTree = Math.max(maxTree, trees[i]);
        }

        int left = 0;
        int right = maxTree;
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (isPossible(mid)) { // mid 높이로 잘랐을 때 가능하면
                result = mid;
                left = mid + 1; // 더 높게 자를 수 있는지 탐색
            } else {
                right = mid - 1; // 높이를 낮춰야 함
            }
        }

        System.out.println(result);
    }

    static boolean isPossible(int height) {
        long sum = 0;
        for (int tree : trees) {
            if (tree > height) {
                sum += (tree - height);
            }
        }
        return sum >= M;
    }
}

3. 이분 탐색 & Parametric Search 판별

1️⃣ 이분 탐색 (Binary Search)

• 데이터가 정렬되어 있는가? (오름차순/내림차순, 또는 정렬 가능)
• 정확히 일치하는 값 또는 조건을 만족하는 첫/마지막 위치를 찾는가?
  • 예: 특정 숫자 찾기, 첫 번째로 10 이상이 되는 인덱스 찾기
• 탐색 범위를 인덱스 기준으로 절반씩 줄일 수 있는가?
• 정렬 후 탐색을 해도 문제 조건에 맞는가? (순서가 중요한 경우 제외)

2️⃣ Parametric Search

• 정답이 수치형 범위(최소~최대)로 주어질 수 있는가?
  • 예: 길이, 시간, 비용, 개수, 높이
• 문제에서 “최대”, “최소” 같은 최적값을 요구하는가?
• 조건 판별 함수(isPossible)로 “가능/불가능”을 판단할 수 있는가? (중간값을 시도해보고 가능 여부를 검사)
• 데이터가 정렬되어 있지 않아도 정답 범위 자체를 탐색할 수 있는가?
• 답이 연속적인 값(숫자)이고, 가능/불가능 경계점이 존재하는가?
  • 예: 높이 15까지 가능, 16부터 불가능 → 경계가 정답