[백준 16637] IF문 좀 대신 써줘 (feat. 이분탐색 정리)

터무니 없는 n의 길이를 보고... 이분탐색인가 했다.
요즘 이분탐색 문제를 자주 풀고 있는데... 뭔가 유형별로 정리가 필요할 거 같아서 정리해본다.

0. 기본 이분탐색 (값이 존재하는가)

int l = 0, r = n - 1;

while (l <= r) {
    int mid = (l + r) / 2;
    if (arr[mid] == target) {
        // 찾음
        break;
    } else if (arr[mid] < target) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

인덱스 유형

Lower Bound

target 이상이 처음 나오는 위치

int l = 0, r = n;

while (l < r) {
    int mid = (l + r) / 2;
    if (arr[mid] >= target) {
        r = mid;
    } else {
        l = mid + 1;
    }
}
// l이 답

Upper Bound

target 초과가 처음 나오는 위치

int l = 0, r = n;

while (l < r) {
    int mid = (l + r) / 2;
    if (arr[mid] > target) {
        r = mid;
    } else {
        l = mid + 1;
    }
}
// l이 답

값의 범위 유형

First True(최소 만족 값)

int l = 0, r = n;

while (l < r) {
    int mid = (l + r) / 2;
    if (arr[mid] > target) {
        r = mid;
    } else {
        l = mid + 1;
    }
}
// l이 답

Last True(최대 만족 값)

int l = left, r = right;
int ans = -1;

while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
        ans = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
System.out.println(ans);

구분	Upper Bound	First True
대상	배열 인덱스	값의 범위
전제	정렬된 배열	단조 조건
조건	arr[mid] > target	check(mid)
목적	위치	값

질문	답
최소 ○○	First True
최대 ○○	Last True
개수	Upper - Lower
처음 ≥	Lower Bound
처음 >	Upper Bound

그렇다면 이 문제는...

9999
10000 100000 100000
9999이상인 값이 제일 처음으로 나오는 위치가 답이다. 따라서 Lower Bound 유형

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        int count = Integer.parseInt(st.nextToken());
        int cCount = Integer.parseInt(st.nextToken());

        ArrayList<Title> titles = new ArrayList<>();

        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            titles.add(new Title(st.nextToken(), Long.valueOf(st.nextToken())));
        }
        titles.sort(Comparator.comparing(title -> title.limit));
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < cCount; i++) {
            Long power = Long.valueOf(br.readLine());

            int left = 0;
            int right = titles.size() - 1;

            while (left < right) {
                int mid = (right + left) / 2;
                Title now = titles.get(mid);

                if (now.limit >= power) {
                    right = mid;
                    continue;
                }
                left = mid + 1;
            }
            sb.append(titles.get(left).name);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static class Title {
        String name;
        Long limit;

        public Title(String name, Long limit) {
            this.name = name;
            this.limit = limit;
        }
    }
}