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를 찾는 것이다.
[3, 6, 9, 13, 17, 24, 39, 57, 73, 92]
middleIndex
를 찾아낸다 여기서는 4가 된다[24, 39, 57, 73, 92]