0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you asking about the meaning of the recurrence in relation to binary search? $\endgroup$ – adrianN Oct 26 '17 at 8:21
  • $\begingroup$ You first spent time explaining that the number of comparisons in each recursive step is $2$ but then you use a recurrence pattern where you set it to $1$. $\endgroup$ – ratchet freak Oct 26 '17 at 8:25
  • $\begingroup$ @adrianN yes exactly.I want to know that after solving the recurrence relation for binary search , then what should it give?it should give the number of comparisons right? but as explained above ,it's not matching $\endgroup$ – laura Oct 26 '17 at 9:22
  • $\begingroup$ @adrianN can you please help me out ? $\endgroup$ – laura Oct 26 '17 at 11:40
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.