I did a binary search recurrence relation using master's theorem and one using the iterative method. With the iterative method I got log2(n). However, with the master's theorem it was case 2 which is log(n).
Is there a reason why the master's theorem doesn't have a base 2 for the logarithm, or am I just doing something wrong?
These methods give an asymptotic analysis using big O notation. And in big O notation we have:
O(logn) = O(log2n) = O(log10n) ...
In other words: the base of the logarithm does not influence the asymptotic analysis, and the outcomes you got are equivalent.
All logarithms are proportional: for any logarithm bases b and d, and any strictly positive real x:
log_b(x) = log_d(x) / log_d(b)
If you are not concerned about a constant factor, then you can interchange logarithms.
Example: the number of bits required to write a number in base 2 is approximately proportional to the number of digits required to write that number in base 10. The proportionality constant is log_10(2) = 1 / log_2(10) =~ 0.301.
