Choose a sorted array
Use up to 32 whole numbers in nondecreasing order. Equal neighbors are welcome. The search leaves your array unchanged.
Choose an example, then apply it to the inputs.
Make the boundaries visible
Build a trace to see the initial interval. Then take one ordering comparison at a time, move back to inspect a decision, or jump to the final boundary.
Your search trace
0 ordering comparisons
- Unresolved indices
[lo, hi) - —
- Possible boundaries
[lo, hi] - —
- Unresolved elements
- —
- Target
- —
- Prefix: < target
- Unresolved:
[lo, hi) - Suffix: ≥ target
- Outlined: next middle index
A boundary sits before its indexed element. Boundary n, marked END, is after the last element and has no element of its own. Scroll the array sideways when needed.
Last completed decision
No ordering comparison has been made yet.
Next ordering comparison
Build a trace to begin.
The final boundary and membership check appear when the interval is resolved.
The count includes only a[mid] < target ordering comparisons. It excludes input validation, rendering and the separate final equality check.
Completed comparisons
No ordering comparisons have been completed yet.
| Comparison | Before [lo, hi) | Middle index | Compared value | Decision | After [lo, hi) |
|---|
Two intervals, one precise answer
Elements still to resolve
[lo, hi) includes lo and excludes hi. Everything before lo is already known to be less than the target. Everything at or after hi is already known to be at least the target.
The next middle index is lo + floor((hi − lo) / 2). A smaller middle value moves lo to mid + 1; otherwise, including equality, hi moves to mid.
Boundaries that can still be the answer
[lo, hi] includes both endpoints. Once lo = hi, no unresolved element remains and the single remaining boundary is the answer.
The result is the first position p where a[p] ≥ target, or n if every value is smaller. Presence is a separate fact: p < n and a[p] = target. An empty array has just boundary 0 and needs zero ordering comparisons.
Keep the trace. Study the ideas.
The companion course, Binary search: precise boundaries, has twelve questions about sorted input, duplicate values, interval updates, insertion boundaries, progress and cost.
- Download the course JSON below.
- Open RecallWeave and choose that file under Bring your own lesson.
- Inspect the course preview, then select Start this deck when you are ready to begin a fresh lesson.
- Use the lesson’s review and practice, then download study notes to keep your answers and explanations.
This explorer keeps its current inputs and trace in this page. Download a trace to keep a copy. The course and guide downloads contain the original course files.