Given this algorithm for binary search where indexes are from $1$ to $n$.
index location (index low, index high) {
{
index mid;
if (low > high)
return 0;
else {
mid = Floor ((low + high)/2) // The floor function
if (x == S[mid])
return mid;
else if (x < S[mid])
return location(low, mid - 1);
else
return location (mid + 1, high);
}
}
I am trying to show that the time complexity of this algorithm is equivalent to the recurrence on an array of size $n$ would be equal to (According to the textbook I am practicing out of):
$W(n) = 1 + W(\lfloor \frac {n} {2} \rfloor)$ for $n > 1$,
$W(1) = 1$
This is to be used in proving that binary search's worst case scenario is $W(n) = \lfloor \frac {n} {2} \rfloor + 1$
Where I am having difficult is suppose that $n = 6$ (or generally that $n$ is even) then it seems that if $x$ is smaller than the middle, that it will recurse on $W (\lfloor \frac {n} {2} \rfloor - 1)$. Do I really need two different recurrences?