HomeConceptsComputer ScienceAlgorithms and Search

Computer Science · Algorithms and Search

Binary Search / Halving the Search Space

Simulation loading

Open Model Lab is preparing the live lab, controls, and graph surface for this concept.

Wrap-up

What you learned

Recommended next: Open concept testCheck whether the core ideas are ready without leaving this concept.
Read next: Graph Representation and Adjacency IntuitionMove from ordered intervals into graph neighborhoods and visible frontiers.

Key takeaway

Binary search works by maintaining one invariant: if the target exists, it is still inside the active low-to-high interval.
Each midpoint comparison can delete half of the remaining positions because the list is ordered.
A far-away target can still be found quickly once the interval keeps halving.

Common misconception

Binary search is not just a slightly faster scan. Its real advantage is using ordered data to discard half the remaining positions without breaking the answer-still-inside invariant.

It does not improve a one-by-one search by a little. It changes the strategy: keep the target inside the active interval while each midpoint check removes half of what remains.

Keep this idea moving

Open the next concept, route, or track only when you want the current model to widen into a larger branch.

Move from ordered intervals into graph neighborhoods and live frontiersAlgorithms and Search

Graph Representation and Adjacency Intuition

Keep one live graph, one local neighborhood, and one frontier cue visible together so graph structure feels readable before traversal rules get formal.

Return to the same list bench and compare search with sorting costAlgorithms and Search

Sorting and Algorithmic Trade-offs

Watch sorting as visible work on a live list so input order, comparisons, and writes stay concrete instead of collapsing into one final answer.

Next in Layered frontier searchAlgorithms and Search

Breadth-First Search and Layered Frontiers

Keep the queue frontier, visited count, and graph layers visible together so breadth-first search reads as a layered process instead of a procedure list.

Stay with this concept

Review, test, or free-play here when you want one more same-concept pass.

More practice optionsReview on the bench · Worked examples

Practice optionReview on the benchReplay the guided setup with the key controls and graphs in sight.
Practice optionWorked examplesCompare against solved walkthroughs after you try the setup yourself.
Practice optionFree play on the benchExperiment freely with the live controls before moving to another concept.

Reference and support

Use these calmer sections when you want a fuller explanation, examples, or accessibility support after the guided flow.

Return here when you want the slower reference pass.

Open reference and support

Equation snapshotMidpoint rule · Interval widthShow 2 equations

The midpoint tells you which value to test next; the interval width shows how the low-to-high invariant shrinks after each comparison.

Midpoint rule
$mi d = ⌊ \frac{l o w + hi g h}{2} ⌋$
Picks the index halfway between low and high, so the next comparison tests the middle of the live interval.
Interval width
$w = hi g h - l o w + 1$
Counts how many positions in the current interval could still contain the target.

Why it behaves this way

Explanation

Binary search only works on ordered data. The invariant is simple: if the target exists, it must still be inside the current low-to-high interval.

Because the values are sorted, one midpoint comparison tells you which half cannot contain the target. Move low or high inward, and the promise stays true.

Watch low, mid, high, and the highlighted interval together. The speed does not come from scanning faster; it comes from preserving the invariant while shrinking the live search space again and again.

Key ideas

01Binary search only works because sorted order lets one midpoint comparison discard a whole half.

02The interval invariant is: the target, if it exists, stays between low and high.

03Low, mid, and high mark the current search space at every step.

Worked examples

Open examples when you want to see the same idea walked through step by step.

Frozen walkthrough

Step through the frozen example

Frozen walkthrough

Use the highlighted interval, midpoint marker, and counters to explain how the invariant survives this step.

Supporter unlocks saved study tools, exact-state sharing, and the richer review surfaces that support this guided flow.

View plans

Frozen valuesUsing frozen parameters

From the live scene, what does this step tell you about where the target can still be?

n

Array size

k

Target position

1. Mark the active interval

The active interval runs from index 0 to 13, so 14 positions are still possible.

2. Compare the midpoint with the target

The current midpoint is index 6, which holds 22 while the target is 25.

3. Compare binary search with a one-by-one scan

So far binary search has used 0 midpoint checks, while a one-by-one scan would need 8 checks to guarantee the same target.

Current interval summary

[l o w, hi g h] = [0, 13], mi d = 6

Because the target is larger than the midpoint value, the left half is already ruled out.

Quick test

Loading saved test state.

Accessibility

Open the text-first descriptions when you need the simulation and graph translated into words.

The simulation shows an ordered array. Markers show low, mid, and high, the active interval highlight shows which positions are still possible, and an optional ghost lane shows how far a one-by-one search would have progressed after the same number of checks.

Graph summary

One graph shows the interval width shrinking over time, one tracks the low, mid, and high indices, and one compares the number of binary-search checks with linear-search checks.

Bench tools and share links

Keep stable concept links and exact-state sharing tucked away until you actually need to relaunch or share the bench.

Try this setup

Jump to a named bench state or copy the one you are looking at now. Shared links reopen the same controls, graph, overlays, and compare context.

Current bench

Middle target preset

This bench is currently showing one of the concept's authored presets.

Open default bench

Featured setups

Far-right target

Open a large ordered list with the target near the far edge, then watch the active interval collapse anyway.

Middle target

Open a simple case where the midpoint lands on or near the target very quickly.

Saved setups

Saved setups are a Supporter study tool. Stable concept links still work for everyone.

Checking saved setup access

Open Model Lab is resolving whether this bench can save locally, sync to an account, or open Supporter-only compare tools.

Copy current setup

Exact-state sharing is part of Supporter. Stable concept and section links still stay available.

Stable links

Progress and next steps

Keep progress signals, starter-track handoffs, and review prompts available without letting them compete with the live lesson flow.

Progress

Loading progress

Loading saved concept progress for this browser or synced account before showing completion status.

Starter track

Step 2 of 6

Algorithms and Search Foundations

Binary Search / Halving the Search Space appears later in this track, so it is cleaner to start from the beginning first.

Previous step: Sorting and Algorithmic Trade-offs

Start from track beginning