Meaning and mechanism
Linear search checks values sequentially, while binary search examines the midpoint of the current range. If you know whether the midpoint is smaller or larger than the target value, you can discard one half of the range using the sorted order.
In the following comparisons, we maintain the condition that if an answer exists, it must be located within the remaining interval. If a range becomes empty, we conclude that there is no value within it.
Relationships and conditions
The number of candidates decreases approximately as n/2ᵏ, so the comparison count grows logarithmically. For the simulation’s duplicate-free list with n≥1, the maximum comparison count can be compared with ⌊log₂n⌋+1.
The cost of sorting must be considered separately from the search cost. When the problem of finding the first and last positions in a list with duplicate values is addressed, the stopping conditions must be adjusted.
What to observe in the simulation
Binary search halves the candidate range at each probe.
The sorted integer list has no duplicates. Both methods use the same list.
Key relationships and symbols
binary steps ≤ ⌊log₂n⌋ + 1
| Symbol | Meaning | Unit |
|---|---|---|
| n | Number of data items | items |
| k | Number of comparisons and range reductions | trial |
Worked example
What does binary search require?
A sorted list · Binary search halves the candidate range at each probe.
Common misconceptions
- Applying only the median comparison rule to an unsorted list does not result in correct binary search.