Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n is the number of elements; T(n) is the number of key comparisons.
| Symbol | Meaning | Unit |
|---|---|---|
| Number of elements in the sorted sequence | elements | |
| Maximum number of key comparisons until a match is found or excluded | comparisons |
T(n)\le\lceil\log_2(n+1)\rceil,\quad T(n)\in O(\log n)The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half that cannot contain it. For n≥1, a balanced search needs at most ceil(log2(n+1)) comparisons, hence O(log n); for n=0 it needs none. In a linked list, repeatedly halving the interval does not give logarithmic access because the middle item is not directly addressable. The sorting cost is not part of the search bound.
The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half that cannot contain it. For n≥1, a balanced search needs at most ceil(log2(n+1)) comparisons, hence O(log n); for n=0 it needs none. In a linked list, repeatedly halving the interval does not give logarithmic access because the middle item is not directly addressable. The sorting cost is not part of the search bound.
Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons.
Defining relation
The equation states the defining relation within its stated domain.
Use the example for Binary search: comparison bound and running time to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half.
Formula cluster
Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons.
Search for 16 in [2,5,8,12,16,23,38]. First compare with 12 and keep the right half; next compare with 23 and keep the left half; the third comparison finds 16. The bound is ceil(log2(7+1))=3. The sequence remains sorted, and every step discards half of the remaining interval.
Find elements quickly in sorted arrays and tables, and distinguish search cost from a linear scan.
Here is how to work through a typical Binary search: comparison bound and running time (Höchstens ⌈log₂(n+1)⌉ Vergleiche bei sortierter Folge.) task step by step:
Task
Use the example for Binary search: comparison bound and running time to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons.
The relation applies only under its stated assumptions.
The relation T(n)\le\lceil\log_2(n+1)\rceil,\quad T(n)\in O(\log n) describes Binary search halves the remaining search interval in a sorted, directly indexable sequence and uses logarithmically many comparisons. In the example Search for 16 in [2,5,8,12,16,23,38]. It applies under the assumptions stated in the background. Validity limit: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half Source: MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays.
First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example Search for 16 in [2,5,8,12,16,23,38]. First compare with 12 and keep the right half; next compare with 23 and keep the left half; the third comparison finds 16. The bound is ceil(log2(7+1))=3. The sequence remains sorted, and every step discards half of the remaining interval. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half Source: MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays.
The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half Source: MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays.
The stated units are: n is the number of elements; T(n) is the number of key comparisons.. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half Source: MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays.
Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: The sequence must be sorted before searching, and its middle element must be accessible efficiently, as in an array. Compare the key with the middle item and discard the half Source: MIT OpenCourseWare 6.006, Recitation 1: asymptotic complexity and binary search in sorted arrays.
Quanta exam set
Curated exam set for "Binary search: comparison bound and running time":
Question (front)
Which formula describes Binary search: comparison bound and running time?
Answer in your set
Question (front)
How do you rearrange Binary search: comparison bound and running time for Defining relation?
Answer in your set
Question (front)
Which common mistake happens with Binary search: comparison bound and running time?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for Höchstens ⌈log₂(n+1)⌉ Vergleiche bei sortierter Folge.: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential