✌️이진탐색 - BinarySearch(feat. 파라메트릭 서치)

▶ 유형

• 이진탐색은 기본적으로 반으로 계속 범위를 쪼개가며 타겟 값을 찾는 기법이다. 그래서 순차탐색이 `O(n)` 걸릴 때 이진탐색은 `O(logN)`이 된다.
• 근데 정렬된 상태를 전제로 둔다. 따라서 총 시간 복잡도는 `O(NlogN)`이다. 
• 양 끝을 L, R로 두고, L과 R의 순서가 역전되는 순간이 종료 조건이다.
• 결정 조건을 가지는 최적화 문제인 파라메트릭 서치의 경우에는, L은 정답이 안돼서 계속 올라가고, R은 정답이 됐음(정답이 아닐 수 도 있음)에도 더 최적인 답이 있을 가능성을 두고 내려간다.

기본적인 형태는 아래와 같다.

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

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

        if (arr[mid] == target) {
            return mid; // 찾은 경우 인덱스 반환
        }

        if (arr[mid] < target) {
            left = mid + 1; // 중간값보다 크면 오른쪽 절반 탐색
        } else {
            right = mid - 1; // 중간값보다 작으면 왼쪽 절반 탐색
        }
    }

    return -1; // 찾지 못한 경우
}

라이브러리에서 갖다가 쓰면 `Arrays.binarySearch()`로 사용할 수 있다. 단순한 이진탐색은 어렵지 않다. 내가 처음 이진탐색에서 어려움을 느꼈던 건 lower bound, upper bound였다.

#Lower Bound, Upper Bound

얘는 보통 언제 쓰냐 하면, 중복된 값이 배열에 존재하고, 어떤 위치에서 찾게 될 지 모르는 상황에 사용한다. lower bound는 타겟 값 이상의 값이 최초로 나오는 경우를 말하고, upper bound는 그 반대다.

 

즉 lower bound는 타겟 값보다 같거나 큰 원소 중 가장 위치값이 작은 값을 찾는 경우다.

public static int lowerBound(List<Integer> arr, int target) {
    int left = 0;                  
    int right = arr.size() - 1;    
    int idx = arr.size();       // 최소위치이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정(min max 개념)

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

        if (arr.get(mid) >= target) {  // 만약에 선택한 원소가 target보다 같거나 크다면
            right = mid - 1;           // 왼쪽에 target이 더 있을 수 있으니 right 갱신
            idx = Math.min(idx, mid);  // 최소 위치값(lower bound) 계속 갱신
        } else {
            left = mid + 1;            // 타겟보다 작으면 left 갱신
        }
    }

    return idx;
}

upper bound는 그 반대인 초과가 되는 순간을 찾으면 되는데, `arr.get(mid) > target`으로 바꾸기만 하면 된다.

잘 생각해보면 lower bound 와 upper bound의 idx 차이 값은 그 타겟 값의 개수가 된다. 따라서 차이가 0이라면 해당 값이 배열에 없다는 걸 자연스럽게 알 수 있다.

 

# 파라메트릭 서치

결정문제라는 걸 갖고, 특정 조건을 만족하는 최소/최대값을 구하는 도구다.

https://www.acmicpc.net/problem/2805

 

백준 나무자르기 문제를 예시로 들어보겠다. 이 문제를 해결할 때, 2가지로 부분을 나눠서 작업한다.

// 특정 높이로 나무들을 잘랐을 때 얻을 수 있는 총 길이를 계산하는 함수
private static long namuCalculateCutLength(int height) {
    long sum = 0;
    for (int tree : trees) { // trees는 배열
        if (tree > height) {
            sum += tree - height;
        }
    }
    return sum;
}

나무를 계속 자르면서 합을 구하고 이진탐색의 조건으로 활용하면 된다.

public static int namuCut() {
    int l = 0;
    int r = len; // 가장 높은 나무의 높이

    while (l <= r) {
        int mid = (l + r) / 2;
        
        if (namuCalculateCutLength(mid) >= m) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return end;
}

이 문제는 결정 조건에 L을 다룬다. 그 이유는 결국 최대값을 구해야되기 때문이다. 최소값을 구할 때는 R을 다루고, 이번 문제처럼 최대값을 다룰 때는 L을 결정조건의 응답으로 사용해야된다. 

▶ 전략

이제 문제를 풀어보면서 익숙해져보자.

https://www.acmicpc.net/problem/10815

 

이진 탐색 그 자체인 문제다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int sanggun[];
    static int find[];
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        sanggun = new int[n];
        for (int i = 0; i < n; i++) {
            sanggun[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        find = new int[m];
        for (int i = 0; i < m; i++) {
            find[i] = Integer.parseInt(st.nextToken());
        }
        // 탐색을 위한 정렬
        Arrays.sort(sanggun);
        sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            sb.append(isExist(find[i])).append(" ");
        }
        System.out.println(sb);
    }

    public static int isExist(int t) {
        int l = 0;
        int r = n - 1; // 양 끝값 세팅
        while (l <= r) {
            int m = (l + r) / 2;
            if (sanggun[m] == t) {
                return 1;
            }
            if (sanggun[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return 0;
    }
}

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!