이진 탐색 (Binary Search)

1. Binary Search?

이진 탐색이란 정렬됀 배열에서 특정한 값을 찾아내는 알고리즘이다.

배열의 중간에 있는 데이터를 선택하여 찾고자하는 값 A와 비교한다.

A가 중간 값보다 작으면 중간 값의 좌측 데이터들을 대상으로, A가 중간 값보다 크면 우측 데이터들을 대상으로 다시 탐색한다.

A를 찾을 때까지 이 과정을 반복하면 된다.

 

2. Code

public class BinarySearch {
    public static void main(String[] args){
        int a = 3;
        int[] arr = {1, 2, 4, 5, 6, 7, 8};

        System.out.println(solution(arr, a));
    }

    public static int solution(int[] arr, int a){
        int index = -1 ;

        int low = 0, high = arr.length - 1;
        while (high >= low){
            int mid = (low + high) / 2;

            if(a == arr[mid]){
                index = mid;
                break;
            }else if(a > arr[mid]) low = mid + 1;
            else high = mid - 1;

        }

        return index;
    }
}

 

3. 시간 복잡도 분석 ( Big O )

탐색할 자료의 개수는

첫번째에 N, 두번째에 N/2, 세번째에 N/4, 네번째에 N/8로써
K번 후에는 (1/2)^KN 개가 남게 된다.
최악의 경우는 남는 자료의 개수가 1개가 남는 경우다.

(1/2)^KN = 1
→ N = 2^K
→  K = log₂N
→  O(logN)