Searching sorted data: bounds, duplicates and proof

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Searching sorted data: bounds, duplicates and proof

Searching asks for an item satisfying a condition, but the required result must be explicit. “Find 6” could mean any matching position, the first matching position or every matching record. A linear search checks positions in sequence and works without sorted input; in the worst case it inspects n elements. Our binary-search implementation returns the first occurrence of a target in a list sorted in nondecreasing order, or −1 if absent. Duplicates are allowed, and preserving their meaning is part of the contract.

The algorithm first computes a lower bound: the earliest position whose value is at least the target, or n if none exists. It maintains a half-open interval [lo,hi), initially [0,n). At each step mid=(lo+hi)//2. If values[mid]<target, positions up to mid cannot be the lower bound, so lo becomes mid+1. Otherwise mid may be the first qualifying position, so hi becomes mid. Using hi=mid−1 would mix inclusive and half-open conventions and can discard a valid candidate. The final equality check distinguishes “first value at least target” from “target actually present”.

The invariant is that every position below lo contains a value less than target, and every position at or above hi contains a value at least target. Sortedness justifies extending one midpoint comparison to a whole region. The interval width hi−lo is a nonnegative integer that strictly decreases. At termination lo==hi, the invariant identifies the lower-bound position. If that position is within the array and equals target, it is the first match; otherwise the target is absent. Both bounds protection and equality are needed to avoid indexing at n or returning a larger value.

Each iteration removes roughly half the candidate positions. For n≥1 there are at most floor(log₂n)+1 midpoint comparisons in this implementation; n=0 executes no iterations. Worst-case time is Θ(log(n+1)) under constant-time indexing and comparison, with O(1) auxiliary state apart from the deliberately retained trace. Sorting an unsorted list before one search may cost more than simply searching linearly. For q searches over stable data, comparing O(n log n+q log n) with O(qn) helps justify the preprocessing investment.

A binary search tree stores smaller keys in one subtree and larger keys in the other under a declared duplicate convention. Search costs O(h), where h is tree height. In a balanced tree, h=O(log n); a degenerate chain can have h=Θ(n). The block gives logarithmic binary-tree search as a teaching expectation, but a technically defensible answer states the balance assumption rather than claiming every binary tree has logarithmic height. The present array implementation does not teach every tree traversal or balancing method; those remain assessed gaps.

Reading the diagram: The array remains [2,6,6,6,9] throughout. Teal intervals show the current half-open candidate region and the darker cell is mid: [0,5) at 2, [0,2) at 1, then [0,1) at 0. On the equal values we retain the midpoint by setting hi=mid, searching left for the first occurrence. On 2<6 we set lo=1. At lo=hi=1 the region is empty, and the final equality check confirms index 1. An excluded hi is a boundary, not a cell to inspect.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def first_index(values, target):
"""First occurrence via lower bound; values sorted nondecreasingly."""
lo, hi = 0, len(values)
trace = []
while lo < hi:
mid = (lo + hi) // 2
trace.append((lo, hi, mid))
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return (lo if lo < len(values) and values[lo] == target else -1), trace
```

Worked example: Find the first 6 in [2,6,6,6,9] using the supplied half-open lower-bound search.

Start lo=0,hi=5,mid=2. The value is 6, so set hi=2 rather than returning immediately.

Now mid=1 with value 6, so hi=1. Next mid=0 with value 2, so lo=1.

The interval is empty at lo=hi=1. values[1]==6 confirms the first occurrence. Trace triples are (0,5,2),(0,2,1),(0,1,0).

Answer: Index 1. Three midpoint comparisons are followed by the final bounds/equality check.

Check your understanding: 1. What result is returned for target 8? 2. Give an unsorted input that breaks the algorithm. 3. Ten thousand queries search a million stable records. Explain preprocessing and identify a case where logarithmic comparisons still do not imply logarithmic total cost.

Answer: 1. −1: the lower bound is index 4 with value 9, which is not equal to 8. 2. [9,2,6] with target 9 excludes index 0 after comparing the midpoint 2 and fails. 3. Sorting once can be amortised over many queries; a linear scan would repeat up to a million comparisons each time. If midpoint access requires traversing a linked list, indexing is not constant time, so O(log n) comparisons do not establish O(log n) total runtime.

Why: Binary search relies on an ordered representation, not simply a midpoint formula. Returning any duplicate is not equivalent to returning the first. Complexity depends on operations and representation. Balanced-tree height is an assumption that must accompany a logarithmic tree-search claim.