cleanUrl: /posts/binary-search-time-complexity-proof
share: true

Binary Search 는 왜 $log(n)$ 으로 시간 복잡도를 설명할까? 시간, 공간 복잡도는 이전에도 다뤄본적이 있지만, 수학적으로 증명할 필요가 있다 여겨 살펴보게 되었다.

이전에 작성했던 글은 Recursive 인데 Big O table 이 포함되어 있다

Recursive(재귀호출) 의 Big O 는 어떻게 될까? leetcode 1342. Number of Steps to Reduce a Number to Zero

참조한 대표적인 contents 는 youtube와 geeksforgeek 이다

Binary Search - Time Complexity

Complexity Analysis of Binary Search - GeeksforGeeks

binary search 의 선제 조건은 입력받은 배열이 sorting 되어 있다는 점이다.

fun binarySearch(arr: Array<Int>, findValue: Int, start: Int, end: Int): Int {
    val middleIndex = (start + end) shr 1
    return if (arr[middleIndex] == findValue) {
        arr[middleIndex]
    } else if (start == end) {
        -1
    } else if (arr[middleIndex] > findValue) {
        binarySearch(arr, findValue, start, middleIndex - 1)
    } else {
        binarySearch(arr, findValue, middleIndex + 1, end)
    }
}

이러한 binary search 함수를 만들었다 recursive 로 구현하였고 우리가 아는 binary search 알고리즘이다

주어진 배열은 다음과 같다

[3, 6, 9, 13, 17, 24, 39, 57, 73, 92]

여기서 우리가 할 일은 24를 찾는 것이다.

Iteration 1

Iteration 2