The binary search comparison bound describes the maximum number of key comparisons required to locate an element in a sorted array. Each comparison eliminates approximately half of the remaining search interval, producing logarithmic worst-case time complexity.
Binary Search Comparison Bound
The binary search comparison bound describes the maximum number of key comparisons required to locate an element in a sorted array. Each comparison eliminates approximately half of the remaining search interval, producing logarithmic worst-case time complexity.
\(C_{\mathrm{max}}(n) = \lfloor \log_{2} n\rfloor + 1 = \lceil \log_{2}(n + 1)\rceil\)
What this formula means
Scientific principle
Principle
Binary search repeatedly compares the target with the middle element of a sorted search interval. Depending on the comparison result, it continues in either the left or right half. The search interval therefore decreases exponentially with the number of comparisons.
Derivation
1. Let n be the number of sorted elements.
2. After one comparison, at most approximately n/2 elements remain.
3. After k comparisons, the remaining interval contains at most approximately n/2ᵏ elements.
4. The search terminates when the remaining interval contains at most one candidate.
5. Therefore, n/2ᵏ ≤ 1.
6. Rearranging gives 2ᵏ ≥ n.
7. The maximum number of comparisons is ⌊log₂ n⌋ + 1, equivalent to ⌈log₂(n + 1)⌉ for n ≥ 1.
Final Result
C_max(n) = ⌊log₂ n⌋ + 1
Complexity
T(n) = Θ(log n)
Recurrence Relation
T(n) = T(⌊n/2⌋) + Θ(1)
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
C_max(n) | Maximum number of key comparisons | Comparison operations |
n | Number of elements in the sorted collection | Elements |
k | Number of search comparisons | Comparison operations |
SI units and conversions
Comparison Count
Dimensionless operation count
Input Size
Number of elements
Complexity Class
Θ(log n)
Conditions of use
The input collection must be sorted according to the search key.
The algorithm uses a middle-element comparison to eliminate approximately half of the remaining interval.
The bound assumes each key comparison takes constant time.
The formula applies to the standard comparison-based binary search algorithm.
Limitations and assumptions
The formula counts key comparisons, not all processor instructions.
An unsuccessful search can require a similar logarithmic number of comparisons.
The best case requires only one comparison when the first middle element matches.
Binary search is not directly efficient on a standard singly linked list because accessing the middle element is not constant time.
The formula does not account for the cost of sorting an initially unsorted collection.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Calculate the maximum number of comparisons required by binary search for a sorted array containing 100 elements. |
| At most 7 key comparisons are required. |
Determine the maximum number of comparisons for binary search on a sorted array containing 1,024 elements. |
| The maximum comparison count is 11. |
Real-world applications
Searching sorted arrays
Database index lookup
Dictionary and symbol-table searches
Searching ordered numerical datasets
Efficient lookup in static data structures
Formula Meaning
The binary search comparison bound describes the maximum number of key comparisons required to locate an element in a sorted array. Each comparison eliminates approximately half of the remaining search interval, producing logarithmic worst-case time complexity.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.