Binary search: the idea
Prerequisites: Sorted arrays, indices, and comparing values.
Binary search requires values in ascending order. It maintains inclusive lower and upper indices. It compares the middle value with the target. If the middle is too small, every value at or before it can be discarded; if too large, every value at or after it can be discarded. The interval shrinks until a match is found or no candidates remain.
Try it
Use the same ascending array as Linear search and choose Last item. Compare value-comparison counts. Try Repeated values: this version returns a matching index, which need not be the first.
Reading the display
The remaining interval stays cyan, discarded values fade, and the current midpoint is pink. A green cell is the returned match.
Time and memory
O(log n) worst-case iterations, O(1) working space. The editor additionally validates sorted order in O(n); that validation is separate from the search.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
An unsorted array invalidates the interval-elimination rule. This editor rejects such inputs instead of silently sorting them. Duplicates are allowed; returning the first match requires a different boundary rule.
Continue exploring
- Linear search — Inspect items one at a time until the target appears.