이진 탐색 알고리즘 Binary Search :: 마이구미

이번 글의 주제는 탐색 알고리즘인 이진 탐색 알고리즘이다.

탐색이 필요할 때 유용하게 쓸 수 있고, 비교적 구현이 쉽다.

글을 읽기 전 https://www.acmicpc.net/problem/2776

백준 알고리즘 2776번 암기왕을 풀어보고 오면 좋다.

일반적으로 기본적인 순차 탐색과 비교하면서 다루겠다.

순차 탐색이란 말 그대로 순차적으로 탐색을 하는 경우다.

누구나 한번쯤은 사용했거나 지금도 사용하고 있는 가장 간단하고 기본적인 방법이다.

아래 소스를 통해 보자.

int[] array = {1,4,2,9,10};
int size = array.length;
int target = 10;

for(int i=0;i<size;i++) {
    if (array[i] == target) {

        break;
    }
}

1,4,2,9,10 이라는 배열이 있고, 10라는 값을 찾을 때 하나의 반복문을 통해 순차적으로 탐색한다.

이 경우 10이 배열의 끝에 존재하기 때문에 끝까지 모든 인덱스를 탐색해버렸다.

그리하여 최악의 경우 시간복잡도로는 O(n) 이 나오게 된다.

그렇기에 데이터가 크면 클수록 성능이 저하된다.

그렇다면 이진 탐색의 경우를 보자.

위키의 정의를 보면 정확하게 나와있다.

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이진 검색은 분할 정복 알고리즘의 한 예이다.

이해하기 어렵지 않을 거라 생각한다.

그렇다면 소스를 보자.

Arrays.sort(arr);

.......

public int binarySearch(int[] arr, int target) {
    int first = 0;
    int last = arr.length - 1;
    int mid;

    while (first <= last) {

        mid = (first + last) / 2;

        if (target == arr[mid]) {
            return 1;
        } else {

            if (target < arr[mid]) {
                last = mid - 1;                        	 
            } else {
                first = mid + 1;                        	 
            }
        }
    }
    return 0;
}

이진 탐색 알고리즘을 사용하기 전에는 무조건 데이터가 정렬이 되어있어야하는 전제가 깔려있어야한다.

이진 탐색 알고리즘은 간단하게 말하자면 절반을 나누면서 걸러낸다.

1. 배열의 중간을 먼저 탐색한다.
2. 중간값이 탐색값이면 중단.
3. 중간값이 탐색값이 아니라면 중간값과 탐색값의 크기를 비교한다.
4. 중간값 > 탐색값 - 중간값의 오른쪽 인덱스들은 제외
5.  중간값 < 탐색값 - 중간값의 왼쪽 인덱스들은 제외

정렬이 되어있기 때문에 4번처럼 비교할 필요가 없기 때문에 절반씩 제외시켜 탐색하게 된다.

이로써 시간복잡도는 최악의 경우에도 O(logn)이 된다.

또한 자바는 Arrays 클래스에는 이진 탐색 메소드가 존재한다.

그렇기 때문에 특별한 경우가 아니라면 구현하지 않고 메소드를 사용하면 된다.

Arrays.binarySearch(array, target);

하지만 본인이 이진 탐색을 구현하지 못한다면 꼭 구현한 뒤 쓰자.

밑에는 백준 알고리즘 2776번 암기왕 소스를 두겠다.

private void solve() {
    int t = sc.nextInt();
    int[] array;
    StringBuilder sb = new StringBuilder();

    while(t-- > 0) {
        int one = sc.nextInt();
        array = new int[one];

        for(int i=0;i<one;i++) {
            array[i] = sc.nextInt();
        }
        Arrays.sort(array);

        int two = sc.nextInt();

        for(int i=0;i<two;i++) {

            sb.append(Arrays.binarySearch(array, sc.nextInt()) > -1 ? "1\n" : "0\n");				
        }
    }
    System.out.println(sb.toString());
}