[Java] Baekjoon 10815번 (이분/이진 탐색)

10815번 문제는

첫째 줄에 N

두번째 줄에 N개의 수(-10,000,000보다 크거나 같고 10,000,000보다 작거나 같은)

세번째 줄에 M

네번째 줄에 M개의 수(-10,000,000보다 크거나 같고 10,000,000보다 작거나 같은)

가 입력으로 주어지고 M의 원소가 주어진 N개의 수 중 값이 있으면 1 없으면 0을 찍어 내는 문제이다.

 

다음 문제를 반복문 for를 사용하여 풀면 시간이 초과된다. 따라서 이분/이진 탐색법을 사용하여야 한다.

 

1. 이분/이진 탐색(Binary Search)란?

이진 탐색은 배열이 정렬(오름차순 기준)되어있다는 전제하에 사용 가능하다.

이진 탐색은 반복할때마다 탐색의 범위를 반으로 줄인다. 순서는 다음과 같다.

1. 배열의 처음과 끝을 기준으로 중간 index를 구한다.
   • 처음(left = 0), 끝(right = 배열의 크기 - 1)
2. 중간 인덱스의 값이 찾으려고 하는 값보다 크다면 left = middle + 1 작다면 right = middle -1

1, 2의 과정을 반복하여 탐색한다.

(소주 뚜껑의 쓰여있는수를 Up&Down으로 중간 값을 이용해 맞춘다고 생각하면 쉽다. 소주 뚜껑에는 1 ~ 50까지의 수가 쓰여 있으므로

이진 탐색을 사용한다면 못해도 6번안에 숫자를 맞출수 있다.)

 

이진탐색의 경우 시간 복잡도의 '빅오 표기법'을 이용하여 확인하였을때 로그 시간인 O(logn)으로써 다른 정렬에 비해 상대적으로 매우 빠르다.

 

 

2. 이진 탐색 구현하기

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

        while (left <= right) {
            int middle = (left + right) / 2;
            if (num > array[middle]) {
                left = middle + 1;
            } else if (num < array[middle]) {
                right = middle - 1;
            } else {
                return 1;
            }
        }
        return 0;

    }