Algorithms and data structures · Intermediate

Discover search bounds by doubling

Search sorted sequences without a known length, defining the end marker, stable reads and first-match boundary behavior.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Discover a finite search bound
  2. Trace the doubling probes
  3. Implement a first-match contract
  4. Measure cost relative to the boundary position
  5. State stability and termination assumptions
  6. Handle index growth and comparison rules
  7. Cross a duplicate run correctly
  8. Exercise: finish after an out-of-range probe
  9. Ask Logeia about this articleCheck your understanding

Discover a finite search bound

Suppose a sorted sequence exposes read(i) but not its length. Valid positions return values and out-of-range positions return None. After checking the first element, probe positions one, two, four and eight until a value reaches the target or the accessor reports the end. That discovers an interval in which ordinary binary search can finish.

The accessor contract is part of the algorithm. None cannot simultaneously mean an ordinary value, a timeout and a missing position. An external service may also charge for reads or reject large indices. Exponential search is not permission to issue unbounded requests without defining those limits. The method requires stable, comparable sequence values and a reliable distinction between a boundary and a failed read.

Trace the doubling probes

For one, three, five, seven, nine, eleven, thirteen, fifteen and seventeen, search for thirteen. After the first element, positions one, two and four contain three, five and nine. Position eight contains seventeen, so candidates are positions five through eight. Everything through position four is too small; position eight must remain because it could have been equal to the target.

If position eight is instead out of range, that does not prove absence. The end may lie between positions five and eight. During binary search, treat an out-of-range response as belonging on the upper side and move left. Once the boundary is found, explicitly compare its value with the target. A lower-bound position is not automatically a successful exact-match result.

Read indexValueCompared with target 13
01Below
13Below
25Below
49Below
817Upper bound; binary search indices 5..8

Implement a first-match contract

The implementation handles position zero separately: empty input returns None, and a first value already above the target proves absence. Otherwise lo starts just beyond the last known-small probe while hi doubles. In the final lower-bound search, a value at least as large as the target, or an out-of-range result, moves hi left. A smaller value moves lo right. A final equality check distinguishes the first matching position from an absent target.

Tests compare duplicate-containing arrays of lengths zero through thirty-nine against bisect_left, including missing values. A real accessor adapter should translate only its documented out-of-range response. Do not catch every exception as an end marker, since authentication and transport failures provide no evidence that the sequence ended.

python
from bisect import bisect_left
def search(read,target):
    first=read(0)
    if first is None:return None
    if first>=target:return 0 if first==target else None
    lo=1;hi=1
    while True:
        value=read(hi)
        if value is None or value>=target:break
        lo=hi+1;hi*=2
    while lo<hi:
        mid=(lo+hi)//2;value=read(mid)
        if value is None or value>=target:hi=mid
        else:lo=mid+1
    return lo if read(lo)==target else None
for n in range(40):
    values=[i//2 for i in range(n)]
    def read(i):return values[i] if i<len(values) else None
    for target in range(-1,23):
        i=bisect_left(values,target);expected=i if i<n and values[i]==target else None
        assert search(read,target)==expected
print('empty, first, duplicate, absent and out-of-range cases passed')

Measure cost relative to the boundary position

If the answer or insertion boundary is at position p, doubling uses O(log(p plus one)) probes. The discovered interval has width proportional to that position, so its binary search has the same order of read calls. Empty input and a first-position answer take a constant number. A very long sequence need not be explored to its far end when the target lies near the beginning.

This counts accessor calls, not necessarily elapsed time. Implementing read(i) by walking a linked list from its head makes individual accesses increasingly expensive. A remote store adds latency, transfer cost, caching and charging units. Estimate the access mechanism separately from the search's read count. Logarithmically many probes only imply logarithmic time when the chosen access-cost assumption is justified.

State stability and termination assumptions

Insertion during the search can change the meaning of indices and move an answer into a previously discarded range. Separate reads may each observe a sorted sequence while still failing to describe one stable sequence. Use a snapshot or versioned accessor when the application requires a result about a specific state. Sortedness at isolated moments is weaker than the stable-input contract used in the proof.

An endlessly growing stream that never reaches the target or an end marker need not terminate. Practical services may impose a deadline, maximum index or read budget. A budget-exhausted result is not proof of absence. Keep incomplete search distinct from the None returned after a completed finite-sequence search. Termination depends on the accessor and data domain as well as on the loop updates.

Handle index growth and comparison rules

Python grows integer indices as needed, but doubling a fixed-width index can overflow. Wrapping to zero or changing sign destroys both interval expansion and termination arguments. A port needs an explicit maximum-index policy, such as saturation followed by a final bounded search. Merely switching to an unsigned type does not eliminate wraparound.

Caching a previous probe may reduce accessor calls when repeated reads of an index are stable. Before optimizing, establish the end marker, comparison order and first-match requirement. Values such as floating-point NaNs need a consistent ordering policy for sorting and searching; ordinary comparisons do not automatically provide the assumed total order. Bounds, accessor behavior and comparison semantics are all part of the implementation contract, not optional details around an otherwise complete loop.

Cross a duplicate run correctly

If target values occupy positions three through seven, an equality at doubling probe four is not yet the first-match answer. Search leftward within the interval after the previous known-small probe. An existence-only interface could return immediately, but this function promises the earliest index. A convenient early observation does not override the output contract.

When caching probes, store the index together with its value. Reusing a value as if it belonged to another position breaks the interval argument. Tests should include duplicate runs and the end marker, confirming that the returned position is valid and no earlier equal value exists. This illustrates how a small interface choice—first occurrence rather than any occurrence—changes both an optimization and the necessary verification.

Exercise: finish after an out-of-range probe

For two, four, six, eight, ten, twelve and target ten, probes at positions one, two and four return four, six and ten. The remaining interval is positions three through four, and the result is four. Change the target to eleven: position four is still too small, so position eight reaches the end marker. Search positions five through eight; the boundary contains twelve, so exact eleven is absent.

For two, two, two, four and target two, the correct result under this contract is position zero. Another match would satisfy a weaker specification but not the first-match promise here. Explain probe values, discarded ranges, the remaining interval and final equality test. In particular, reaching the end marker only bounds the search; it does not by itself establish absence.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path