What is the worst-case and average-case time complexity of the Binary search?

Concept: Binary search only works on a sorted collection. Each comparison against the middle element eliminates one half of the remaining search space, so the number of comparisons T(n) needed for n elements follows the recurrence T(n) = T(n/2) + O(1), which solves to T(n) = O(log n).

Application (worked example): Trace the halving on a sorted array of 16 elements while searching for a value:

1. Start with 16 candidate elements; compare the target with the middle element and discard the half that cannot contain it -> 8 candidates remain.

2. Compare again with the new middle element; discard half again -> 4 candidates remain.

3. Repeat the halving -> 2 candidates remain.

4. Repeat the halving once more -> 1 candidate remains.

5. A final comparison against the single remaining candidate determines whether it matches the target -> the search ends.

That is 5 comparisons in the worst case for 16 elements -- in general, at most ⌊log2(n)⌋ + 1 comparisons for n elements, which is still the same O(log n) order as the recurrence solved above.

Cross-check / contrast: The decision tree describing every possible sequence of comparisons has depth ⌊log2(n)⌋ + 1. A successful search can terminate earlier than this worst-case depth, but the AVERAGE number of comparisons across all possible outcomes (found at any position, or not found) is also Θ(log n) -- close to, but generally slightly below, the worst-case count; only the constant factor differs between worst and average case, not the asymptotic order. Contrast this with a linear scan, which checks one element at a time without discarding any others and is O(n); and with O(n log n), which is the typical cost of comparison-based SORTING (e.g. merge sort), not of a single search over an already-sorted array. The table below contrasts the growth rate against the other complexities offered:

Result: The search space shrinks geometrically (by a factor of 2) at every step rather than linearly, so both the worst-case and the average-case time complexity of binary search is O(log n).