✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2065

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

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.

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

Calculate the maximum number of comparisons required by binary search for a sorted array containing 100 elements.

  • Given: n = 100.

  • Use: C_max(n) = ⌊log₂ n⌋ + 1.

  • log₂ 100 ≈ 6.644.

  • ⌊6.644⌋ = 6.

  • C_max = 6 + 1 = 7.

At most 7 key comparisons are required.

Determine the maximum number of comparisons for binary search on a sorted array containing 1,024 elements.

  • Given: n = 1,024.

  • Use: C_max(n) = ⌊log₂ n⌋ + 1.

  • Since 1,024 = 2¹⁰, log₂ 1,024 = 10.

  • C_max = 10 + 1 = 11.

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.

← Back to Formula Hub · Suggest a correction or source