Use the master method to show that the solution to the binary-search recurrence $T(n) = T(n/2) + \Theta(1)$ is $T(n) = \Theta(\lg n)$. (See Exercise 2.3-5 for a description of binary search.)

In the given recurrence, $a = 1$ and $b = 2$. Hence, $n^{\log_b a} = n^0 = 1$ and $f(n) = \Theta(1) = \Theta(n^{\log_b a})$. Hence case 2 of master method applies.

Hence, $T(n) = \Theta(n^{\log_b a} \lg n) = \Theta(\lg n)$