Binary search needs order and a shrinking interval

By UK GCSE Computer Science · independent study · myAudience

Original AI-generated teaching raster via built-in image_gen; author inspected 2026-10-04. · Generated project artwork; no copied exam or publisher illustration. Independent rights/publication review pending.

Binary search needs order and a shrinking interval

Binary search uses sorted order to remove impossible candidates. Its contract here requires values sorted ascending and returns some matching index, or -1 if absent; duplicates do not promise the first occurrence. Entry skills are linear search, inclusive bounds and integer division. The algorithm chooses the midpoint of the current candidate interval. If target is less than the midpoint value, all positions from midpoint upward are too large; if greater, all positions through midpoint are too small. Without the sorted precondition, this argument collapses even if the loop still terminates.

Represent the interval with inclusive low and high indices. Initially low=0 and high=n-1; an empty list has high=-1 and immediately fails low<=high. Choose middle=(low+high)//2. After a smaller target set high=middle-1; after a larger target set low=middle+1. Removing the midpoint is essential because it has already been shown not to match. Setting low=middle on a two-element interval can repeat the same middle forever. The invariant says any possible match remains between the bounds; the number of candidates strictly decreases on each unsuccessful iteration.

The raster traces sorted values 3,8,12,19,24,31,42 and target 31. Initially (low,high,middle)=(0,6,3) and value 19. Then low becomes 4; (4,6,5) gives value 31 and succeeds. Searching 30 instead continues to interval (4,4), checks 24, then reaches (5,4) and fails. Keep indices distinct from values in the table. The algorithm can be correct while a trace is wrong if the writer replaces an index with a data value.

At most roughly half the candidates remain after each unsuccessful midpoint probe. For n=7 the worst number of probes is three; doubling a large sorted data set adds about one probe. The optional enrichment description is logarithmic growth under fixed-cost indexing and comparisons, not an requirement to perform formal complexity proofs. Our count is midpoint probes: Python may perform an equality and an order comparison during one probe, so it is not identical to linear search's equality-comparison metric. Sorting an initially unsorted list has a cost and may outweigh the saving for one search; repeated searches on unchanged sorted data are a different workload.

Python list random access makes the midpoint available directly. An abstract linked sequence would need extra traversal, changing the cost model. Validating sortedness on every call also costs a full pass; this implementation assumes the caller already guarantees it. That assumption must be documented, tested at the integration boundary and preserved by updates. A failing unsorted example is not “bad luck”; it is a broken precondition. The transfer asks for a different duplicate contract and therefore a modified invariant rather than a superficial new target.

Runnable original Python 3 example (also saved verbatim in examples for CLI execution):
```python
def binary_search(values, target):
"""Return (some matching index or -1, midpoint probes); sorted ascending."""
low = 0
high = len(values) - 1
probes = 0
while low <= high:
middle = (low + high) // 2
probes += 1
if values[middle] == target:
return middle, probes
if target < values[middle]:
high = middle - 1
else:
low = middle + 1
return -1, probes

assert binary_search([3, 8, 12, 19, 24, 31, 42], 31) == (5, 2)
assert binary_search([3, 8, 12, 19, 24, 31, 42], 30) == (-1, 3)
assert binary_search([], 30) == (-1, 0)
```

Worked example: Trace absent target 30 in the seven-card visual.

Probe index 3, value 19; choose low=4.

Probe index 5, value 31; choose high=4.

Probe index 4, value 24; choose low=5. Now low>high, so return -1.

Answer: Absent after three midpoint probes.

Check your understanding: Transfer: find the first 5 in [2,5,5,5,9]. Propose a modification and explain why returning immediately on equality violates the new contract. Also discuss whether sorting 1000 unsorted values just for one lookup is automatically preferable to linear search.

Answer: Remember a matching midpoint as candidate and continue left by setting high=middle-1. Return the remembered candidate when the interval is exhausted; result is index 1. Immediate equality may return index 2. Sorting is additional work and changes order, so one lookup does not automatically justify it.

Why: Continuing left searches for an earlier match while retaining a known valid one. Candidate must start at -1 to represent absence. Efficiency is about the complete task under its preconditions, not just the isolated search loop.