이진 탐색(Binary Search) (Java)

 

이진 탐색이란?

"정렬된 배열"에서 특정한 값을 찾아내는 알고리즘

배열의 중간 값과 찾고자 하는 값을 비교하면서 탐색한다. 찾고자 하는 값이 X라고 하면, X가 중간 값보다 작으면 좌측 데이터를 대상으로, X가 중간 값보다 크면 우측 데이터들을 대상으로 다시 탐색한다. 해당 과정을 X를 찾을 때까지 반복한다.

 

시간 복잡도

전체 데이터 수를 N이라고 하자.

 

1) 첫 번째 탐색 후 절반만 남아 남은 수가 N/2개

2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 N/2 ×1/2개
3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 N/2 ×1/2 ×1/2개

...
k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 (1/2)^k * N이 된다.

 

최고의 경우 

 

중간 값이 찾고자 하는 값인 경우에는 한 번에 탐색이 가능하므로 O(1)이다.

 

최악의 경우

 

탐색 마지막에 찾고자 하는 값이 나온 경우

즉, 남은 탐색할 데이터 개수가 1개인 경우에 가장 많은 탐색을 하게 된다.

 

위의 식을 가지고 계산을 진행해 보자.

(1/2)^k * N ≈ 1 

 

양 변에 2^k를 곱해준다.

 2^k ≈ N

 

양 변에 2를 밑으로 하는 로그를 취한다.

k ≈ logN

 

따라서 자료의 개수 N에 따른 시행 횟수는 logN

즉, 시간복잡도는 O(logN)이 된다.

 

* 평균 시간 복잡도도 O(logN)과 같다.

 

구현 과정

 

1) 처음 low를 0, high를 arr.length() - 1, mid를 (low+high)/2로 둔다.

찾고자 하는 값을 target이라 할 때, arr[mid]와 target을 비교한다.

 

2) target < arr[mid]이므로 end의 값을 mid - 1로 바꾼 후 다시 탐색한다.

즉, 다음 탐색에서는 index 0 ~ 3까지 탐색한다.

 

3) 새로운 중간 값 target > arr[(0+3)/2]이므로 start값을 mid + 1로 바꾼 후 다시 탐색한다.

즉, 다음 탐색에서는 index 2 ~ 3까지 탐색한다.

 

4) arr[mid]가 target과 일치하므로 탐색을 종료한다.

 

구현 코드

반복문

 

public class BSearchLoop {
    static int[] arr = {0, 1, 2, 3, 4, 5, 6};
    static int target = 1;

    public static void main(String[] args) {
        System.out.println(binarySearch());
    }

    static int binarySearch() {
        int start = 0;
        int end = arr.length - 1;
        int mid;

        while (start <= end) {
            mid = (start + end) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (target < arr[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1;
    }
}

 

재귀

 

public class BSearchRecursion {
    static int[] arr = {0, 1, 2, 3, 4, 5, 6};
    static int target = 1;

    public static void main(String[] args) {
        System.out.println(binarySearch(0, arr.length - 1));
    }

    static int binarySearch(int start, int end) {
        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (target < arr[mid]) {
            return binarySearch(start, mid - 1);
        } else {
            return binarySearch(mid + 1, end);
        }
    }
}

 

 

Reference

https://cjh5414.github.io/binary-search/

https://kangworld.tistory.com/65

https://minhamina.tistory.com/127

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/