The recurrence T(n) = T(n/2) + O(1) for binary search solves to

Each step halves n, so after k steps the size is n/2^k. Reaching size 1 needs k = log₂ n steps, each doing constant work. Total: O(log n). Master theorem case 2 gives the same answer (a = 1, b = 2, d = 0; a = b^d so result is O(n^0 log n) = O(log n)).