Inputs
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 3 | 9 | 10 | 14 | 19 | 20 | 21 |
K = 21, i = 0, j = 7
Algo
func binarySearch(arr, i, j, k):
mid = (i+j)/2
if (arr[mid] == k):
return mid
if (i == j):
return -1
if (arr[mid] < k):
return binnarySearch(arr, mid+1, j, k)
return binnarySearch(arr, i, mid, k)Time Complexity
Let Input Size = n
Recursive Equation
T(n) = T(n/2) + O(1)
Recursion Tree
n --- O(1)
n / 2 --- O(1)
n / 4 --- O(1)
n / 8 --- O(1)
.
.
1
Height of the Tree