How many comparisons will binary search make in the worst case using this algorithm?
algorithm, arrays, binary-search, complexity-theory
Solution
The worst-case in this case is, if the element K is not present in A and smaller than all elements in A. Then we have two comparisons in each step: `K > A[m]` and `K < A[m]`.
For in each step the array is being cut into two parts, each of the size `(n-1)/2`, we have a maximum of `log_2(n-1)` steps.
This leads to a total of `2*log_2(n-1)` comparisons, which asymptotically indeed equals to `O(log(n))`.
Problem
Hi there below is the pseudo code for my binary search implementation: ``` Input: (A[0...n-1], K) begin l ← 0; r ← n-1 while l ≤ r do m ← floor((l+r)/2) if K > A[m] then l ← m+1 else if K < A[m] then r ← m-1 else return m end if end while return -1 // key not found end ``` I was just wondering how to calculate the number of comparisons this implementation would make in the worst case for a sorted array of size n? Would the number of comparisons = lg n + 1? or something different?