A binary search on a sorted array of n elements takes ________ time in the…

Binary search is a divide-and-conquer technique that works only on a sorted array. At each step it compares the target value with the array's middle element and discards the half of the remaining range that cannot contain the target, so the range still to be searched shrinks by a constant fraction — one half — after every comparison.

1. Start with a sorted array of n = 16 elements; the full array is the current search range.

2. The first comparison, against the middle element, discards one half, leaving 16 / 2 = 8 elements still to search.

3. Repeating this halving reduces the range to 4 elements after the 2nd comparison, 2 elements after the 3rd comparison, and exactly 1 element after the 4th comparison.

4. Reaching a single remaining candidate took 4 comparisons, since 16 = 24, so 4 = log216; in general, for an array of n elements, shrinking the range down to a single remaining candidate takes log2n comparisons, rounded down to the nearest whole number — exactly that many when n, like 16, is a power of two.

5. That last remaining candidate has not yet been checked, so one further comparison is required to confirm whether it matches the target — giving a worst-case total of log2n (rounded down) + 1 comparisons; for n = 16 this is 4 + 1 = 5 comparisons.

6. Since rounding down and adding this constant '+1' does not change how the comparison count scales with n, the worst-case running time is still proportional to log n, i.e. O(log n).

This matches the standard recurrence for binary search: one comparison (O(1) work) reduces the problem to searching a range half the size, i.e. T(n) = T(n/2) + O(1). Substituting this relation into itself repeatedly — exactly mirroring the step-by-step halving traced above — again yields T(n) = O(log n), independently confirming the result.