[Algorithm] 이분 탐색 유형 모음

Lower Bound

Lower Bound는 정렬된 배열에서 특정 값(= 키 값) 이상이 처음으로 나타나는 위치를 찾는다.
=> 즉, 주어진 값 이상인 첫 번째 원소의 인덱스를 반환한다.

 

특징

• 중복된 값이 존재할 때, 가장 처음 등장하는 위치를 반환
• 값이 존재하지 않으면 삽입될 첫 번째 위치를 반환

import java.util.Arrays;

public class LowerBoundExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 4, 7, 9};
        int target = 4;
        int index = lowerBound(arr, target);
        System.out.println("Lower Bound Index: " + index);
    }

    static int lowerBound(int[] arr, int key) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= key) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

Lower Bound Index: 2

---

Upper Bound

Upper Bound는 정렬된 배열에서 특정 값(= 키 값)보다 큰 값이 처음 나타나는 위치를 찾는다.
=> 즉, 주어진 값보다 큰 첫 번째 원소의 인덱스를 반환

 

특징

• 중복된 값이 존재할 때, 가장 마지막을 지나치는 위치를 반환
• 값이 존재하지 않으면 배열의 길이를 반환

public class UpperBoundExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 4, 7, 9};
        int target = 4;
        int index = upperBound(arr, target);
        System.out.println("Upper Bound Index: " + index);
    }

    static int upperBound(int[] arr, int key) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

Upper Bound Index: 5

 

만약 중복된 값이 존재할 때, 그 중 가장 마지막 위치를 찾고 싶다면?
=> upper bound index - 1을 해주면 된다.
=> upperBound의 반환 값에서 left가 아닌 left - 1을 해주자.

---

Parametric Search

Parametric Search는 최적화 문제를 '예/아니오' 결정 문제로 변환하여 해결하는 기법이다.
이분 탐색을 사용해 가능한 범위에서 최적의 해를 찾을 수 있다.

 

사용 예시: 예산 배분, 최소/최대 작업 시간, 나무 자르기 문제 등

 

중요 포인트

• left, right 값의 범위
• key 값이 무엇인지 설정하기
• Upper Bound 문제인지, Lower Bound 문제인지 확인

예시 문제 1: 나무 자르기

백준 2805번: 나무 자르기(S2)

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());
        int M = Integer.parseInt(st.nextToken());

        long[] trees = new long[N];
        st = new StringTokenizer(br.readLine());
        long right = -1;
        for (int i = 0; i < N; i++) {
            trees[i] = Long.parseLong(st.nextToken());
            right = Math.max(right, trees[i]);
        }

        long left = 0;
        long mid;

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

            // 얻을 수 있는 총 나무 높이 구하기
            long ret = 0;
            for (long tree : trees) {
                if(tree > mid) ret += (tree - mid);
            }

            // 최대 높이를 구하는 것이므로 Upper Bound로 해결
            // Upper Bound: 최초로 필요 길이(M)을 넘는 값
            if(ret < M) right = mid; // 부족하면 낮추기
            else left = mid + 1; // 충분히 가져갈 수 있으면 더 높이 잘라보기 
        }

        System.out.println(left - 1); // Upper Bound는 '최초로 필요 길이(M)을 넘는 값'이므로, 그 이전 값인 left-1을 출력
    }
}

예시 문제 2: 공유기 설치

백준 2110번: 공유기 설치(G4)

public class Main {

    static int[] house;

    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());
        int C = Integer.parseInt(st.nextToken());

        house = new int[N];

        for (int i = 0; i < N; i++) {
            house[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(house);

        int left = 1, right = house[N - 1] - house[0] + 1, mid = 0;

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

			// 설치 가능한 공유기 수가 최대가 되도록 하는 값을 구하고 싶음
            // -> Upper Bound
			// 최소 거리가 mid일 때, 설치가능한 공유기 수가 C보다 작다면
            if (getInstallableCnt(mid) < C) right = mid; // 범위를 줄임
            else left = mid + 1; // 크거나 같다면 범위를 늘림
        }

        System.out.println(left - 1);
    }

	// 최소 거리가 distance일 때, 설치 가능한 공유기의 수
    private static int getInstallableCnt(int distance) {
        int count = 1;
        int lastLocate = house[0]; // 반드시 첫 집에는 공유기를 둔다고 가정

        for (int i = 1; i < house.length; i++) {
            if (house[i] - lastLocate >= distance) {
                ++count;
                lastLocate = house[i];
            }
        }

        return count;
    }
}