이진 탐색 (Binary Search) 시간 복잡도가 왜 logn일까?

    public static int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;

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

            if(nums[mid] == target) {
                return mid;
            }

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

        return -1; // target 없음
    }

 

이진 탐색은 divide and conquer의 개념을 가지고 있다. 

시간 복잡도는 O(logn)이 되는데, 처음에는 탐색해야 할 데이터가 N개라면 N개 모두가 탐색 범위가 된다. 그 이후 
다음 탐색에서 탐색 범위는 절반으로 줄어 N/2 가 되고 그 다음 탐색에서 탐색 범위는 또 절반으로 줄어 N/4가 되고 그 다음은 N/8, N/16 이 되게 된다.

즉 탐색해야 하는 횟수가 k 라면 N개의 데이터를 탐색하는 데 N = 2^k가 된다. 

k의 값을 구하려면 k = log2(N)이라 할 수 있다.

 

로그가 약한 사람들을 위한 팁

log2(8) 은 2를 몇 제곱 해야 8이라는 값을 얻을 수 있느냐는 뜻이다. log2(2^3) 이며 이는 3log2(2)로 표현 할 수 있다. 

log2(2), log3(3) ... 등은 값이 일이므로 3log2(2) = 3 이 된다. 

즉 2^3 = 8 이고 3 = log2(8)이 된다. 

위에서 탐색 범위는 2^k = N  이므로 이를 로그로 표현하면 k = log2(N)이라고 할 수 있다!