이진탐색(Binary Search)

이진탐색

이진탐색이란 한 번 비교를 거칠 때마다 탐색 범위가 반(1/2)으로 줄어드는 탐색 방법입니다. 순차탐색에 비해 얼마나 빠른 알고리즘이냐면 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다.

이진 탐색 과정

1~7까지 정렬되어 있는 수에서 5를 찾는 과정이다.

1~7까지의 정렬된 수가 주어짐

1) mid 값 = (0 + 6) / 2 = 3 

[3]의 값인 4보다 찾고자 하는 값이 큼

2) 인덱스 4~6까지 검색, mid값 = 5

[5]의 값인 6보다 찾고자하는 값이 더 작음

3) 4 ~4까지 검색, mid 값 = 5

찾고자하는 값을 찾음

총 3번의 비교 연산이면 원하는 값을 찾을 수 있음!

이진 탐색의 성능

데이터 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어 진다.

n x (1/2)k = 1

n x 1/2k = 1

n = 2k

k = log2n

이진 검색의 구현

Iterative한 구현

    public static int binarysearch(int[] arr, int target){
        int low = 0, high = arr.length - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(target < arr[mid]){
                high = mid - 1;
            }
            else if(target > arr[mid]){
                low = mid + 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }

recursive한 구현

    public static int binarysearch(int[] arr, int left, int right, int target){
        // 예외 처리(target값이 arr에 아예 없는 경우)
        if(right < left){
            return -1;
        }
        int mid = (left + right) / 2;
        if(target < arr[mid]){
            return binarysearch(arr, left, mid - 1, target);
        }
        else if(target > arr[mid]){
            return binarysearch(arr, mid + 1, right, target);
        }
        else{
            return mid;
        }
    }