Number of comparisons in Binary search

Question

I know this question is very trivial to ask, but I have got some doubt while solving this problem.Code is given below

public class BinarySearch {
public static int binSearch(int a[], int x) { // a is sorted
int low = 0, high = a.length - 1;
while (low <= high) {
 int mid = (low + high) / 2;
 if (x < a[mid])
 high = mid - 1;
 else if (x > a[mid])
 low = mid + 1;
 else
 return mid;

}

return Integer.MIN_VALUE;

}

If we want to calculate the worst case comparisons of binary search,then

it will be $2 \log n+1$, because $\log n+1$ for checking (low<=high) and $\log n$ for (x < a[mid]) or if (x > a[mid]).

Alright , i have no issue here , i can happily say that worst case comparison for Binary search is $2\log n +1$

---

I faced issue when i tried to solve the recurrence equation, given as-:

$$T(n)=T(\frac{n}{2})+1$$

$\text{Base Case}\,\,T(1)=1$

$T(\frac{n}{2})=T(\frac{n}{4})+1$

Generalizing the equation i got-:

$T(n)=T(\frac{n}{2^{k}})+1+1..+1(k \text{times})$

$T(n)=T(\frac{n}{2^{k}})+k$

$\frac{n}{2^k}=1$

$k=\log n$

So $T(n)=\log n+1$ What actually this value signifies? Is it Minimum number of comparison? Confused Please help me out

Answer 1

The value that you've got is the number of searches required in the worst case by binary search. Each function call is responsible for only 1 search. And your recurrence relation justifies that. So the recurrence relation you wrote is for the number of searches. Indeed we require $\log n +1$ searches if it's a worst case. Take any $n$, say $n=7,8$, and try and see for yourself.

Answer 2

The recurrence is supposed to express the worst-case runtime of binary search on an input of size $n$ (the letter $T$ might stand for time). The range you have to search search is halved in each step, so you get the $T(n/2)$ term on the right side.

Most of the time people only count the comparisons of the data, not the extra comparison for the loop condition, so it takes 1 comparison to halve the search space. For your analysis you might want to write a $+2$ instead of the $+1$, since you do count the loop condition.

As we want to express the worst case runtime, we assume that the element is not in the array, so the recursion terminates only when there is just one element left. This provides us with the base case of $T(1)=1$.

Answer 3

It's an upper bound on the number of comparisons. It's not lower bound because in the best case, you find $x$ immediately (its the middle element), but in the worst case, $x$ isn't in the array, so you had to dive down till the base case in the recursion.

Answer 4

@laura the 2logn+1 is the number of search comparisons happening in the worst case.

But the recurrence relation that you are using i.e. T(n) = T(n/2) + 1 is the Worst-case Time complexity recurrence relation of the Binary Search and not the number of searches that are being done in binary search in the worst case.

Both notions are different things the first one talks about the comparisons in worst case and the second one talks about the running time in worst case.