[알고리즘] Binary Search(이진 탐색 / 이분 탐색)

Binary Search란? 

이분 탐색 알고리즘은 정렬되어 있는 배열(혹은 특정 범위)에서 특정한 값을 찾아내는 알고리즘이다.

배열에 중간에 있는 값을 선택하여 찾는 값과 비교해서 값을 찾아낸다.

중간 값이 찾는 값보다 작으면 중간 값을 기준으로 오른쪽 범위에서 다시 탐색, 크다면 왼쪽 범위에서 다시 탐색을 한다.

탐색을 반복하면서 찾는 값이 일치할 때와 왼쪽 값이 오른쪽 값보다 커지면 종료가 된다.

이분 탐색 과정

해당 배열에서 찾는 값이 16일 경우, 인덱스 0과 5부터 시작을 하고 중간 값은 (0 + 5) / 2 = 인덱스 2가 된다.

중간 값 설정
일반적으로 mid = (left + right) / 2로 계산이 가능하지만, left + right가 자료형의 최댓값을 초과할 경우 오버플로가 발생해 값이 이상하게 나올 수 있는데, 이를 방지하고자 left + (right - left) / 2로 하게 되면 오버플로를 방지하고 동일하게 중간 값을 구할 수 있다.

중간 값 21은 찾는 값 16 보다 크므로, 중간 값이 오른 값이 돼 왼쪽 범위에서 다시 탐색을 한다.

16으로 중간 값이 찾는 값과 일치하면서 종료가 된다.

Binary Search에 사용되는 방법

단순한 이분 탐색(이진 탐색)

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {10, 16, 21, 29, 35, 40};
        int target = 16;
        int answer = -1;

        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (array[mid] < target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid;
            } else {
                answer = mid;
                break;
            }
        }

        System.out.println(answer);
    }
}

투 포인트 탐색

두 배열을 가지고 특정 값을 찾아내거나 한 배열 안에서 양쪽에서 특정 값을 찾아낼 때 등 사용할 수 있다.

두 배열의 교집합 구하기

public class BinarySearch {
    public static void main(String[] args) {
        int[] array1 = {8, 4, 15};
        int[] array2 = {20, 15, 8, 35};
        Arrays.sort(array1);
        Arrays.sort(array2);

        int left = 0;
        int right = 0;
        List<Integer> list = new LinkedList<>();
        while (left < array1.length && right < array2.length) {
            // 값이 작은 쪽의 포인터가 앞으로 이동
            if (array1[left] < array2[right]) {
                left++;
            } else if (array1[left] > array2[right]) {
                right++;
            } else {
                list.add(array1[left]);
                left++;
                right++;
            }
        }

        System.out.println(list);
    }
}

이분 탐색 중 매개 변수 탐색

이분 탐색 중에 다른 변수를 찾아야 하는 경우들이 있다.

백준 2343 - 기타 레슨

public class BinarySearch {
    /*
    * 강의를 배열에 넣어주고 가장 큰 강의 길이와 강의의 총길이를 구한다.
    * 강의를 넣은 배열을 오름차순 정렬해준다. x -> 문제의 조건에 정렬을 하면 안된다.
    * 가장 큰 강의와 강의의 총길이 사이에서 이분 탐색을 한다.
    * 이분 탐색을 하면서 중간값을 기준으로 강의를 블루레이에 나눠담는다.
    * 블루레이의 개수가 주어진 개수보다 많으면 left를 키워 블루레이의 크기를 키워 개수를 줄인다.
    * 블루레이의 개수가 주어진 개수와 같거나 적으면 right를 줄여 블루레이의 크기를 줄여 개수를 늘린다.
    * */
    static int[] lecture;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        int sum = 0;
        int max = 0;
        lecture = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // 입력값을 받으면서 가장큰 강의 길이와 강의의 총길이를 구한다.
        for (int i = 0; i < N; i++) {
            lecture[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum += lecture[i];
            max = Math.max(max, lecture[i]);
        }
        bufferedReader.close();

        System.out.println(binarySearch(max, sum, M));
    }

    public static int binarySearch(int left, int right, int target) {

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

            // 블루레이에 강의 나누기
            int total = 0;
            int cnt = 1;
            // 앞부분 부터 잘라서 기준이 되는 블루레이 크기 비교해 넘어가면 다음 블루레이로 초기화해 계산
            for (int i = 0; i < N; i++) {
                if (total + lecture[i] > mid) {
                    cnt++;
                    total = 0;
                }
                total += lecture[i];
            }

            if (cnt > target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

Binary Search에서 중요한 점

1. 이분 탐색을 하기 위해서는 꼭 배열을 정렬시킨 후 탐색을 해야 한다. (단, 간혹 문제에서 정렬을 사용하지 못하게 하는 문제들이 있는데, 그 경우들은 대부분 배열이 기준이 아닌 다른 값이 탐색의 범위가 될 경우가 많다.)
2. 탐색의 기준이 배열이 될지 다른 값의 범위가 될지를 잘 판단해야 한다. 배열의 인덱스를 가지고 탐색을 할 수 도 있고 다른 범위에서 비교를 할 때 주어진 배열을 사용할 수 도 있다.
3. 좌우 움직임의 조건을 상황에 따라 잘 조절해야 한다. 항상 좌우 값이 중간 값에서 1씩 움직이는 것이 아닐 수 도 있고 정답 값이 중간 값이 아닌 좌우 값이 될 수 도 있다.