I understand that a widely-used recursive equation for the Binary Search is as follows: $$ \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n}{2}) + 1, \quad n>1 \end{align} $$
In order to solve the recursive equation we would simply transform the domain by setting $n = 2^k$, write the transformed equation, go through the telescoping and all that good stuff...
Anyway, my professor said that sometimes there may be an odd number of elements in a sorted list, in which case the equation would look like: $$ \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n-1}{2}) + 1,\quad n>1 \end{align} $$
Then I wondered, how would I perform a domain transformation on such an equation?
Thank you very much!
In the case that $n$ is an odd number, we can just use $n=2k+1$. You'll end up with $$T(2k+1)=T\left(\frac{2k+1-1}{2}\right)+1$$ I'll let you take care of the rest.