English

Searching: Linear and Binary Search

Middle schoolComputer ScienceExact search of a sorted array of unique even integers, zero-based indices

Unlock this lab with a pass

A pass opens every simulation on the site, including Present mode for class. The teaching notes below stay free for everyone.

See passesI already have a pass

One-time payment, no subscription.

About this experiment

Search for the same target with linear search and binary search side by side. Each step performs one comparison in each unfinished algorithm. Binary search probes the middle of its remaining sorted interval; linear search advances one position at a time. Select an odd target to see both algorithms finish without finding a match.

Learning goals

  • Trace the candidate interval and midpoint in binary search
  • Compare linear and binary search comparison counts
  • Explain why binary search requires sorted data and handles absent targets

How to use it

  1. 1Search for 32 in the default array, advancing one comparison at a time.
  2. 2Note when binary search finishes, then continue until linear search finishes.
  3. 3Choose an odd target such as 31. Inspect how binary search reaches an empty interval.
  4. 4Change the array length and search for its last value. Compare the worst-case bounds.

The model

Binary-search midpoint for inclusive low and high indices
Upper bound on binary-search value comparisons
Worst-case comparisons for the linear search shown

Assumptions

  • The array contains ascending unique even integers 2, 4, ..., 2n. Indices start at zero.
  • A value comparison is a single three-way comparison with the target. Index arithmetic and loop checks are not counted.
  • Linear search scans the whole array when the target is absent, without using an early-stop optimization from sorted order.
  • Each row stays on its completed state while the other search continues. The current candidate interval is shown before the current probe result is applied.

Try this in class

  1. Q1Why is binary search allowed to discard half the remaining positions after one comparison?
  2. Q2How many comparisons are needed to find the last value in an array of 32 values using each method?
  3. Q3What fails if the same midpoint rule is applied to an unsorted array?

Frequently asked questions

Why does binary search fail for an odd target?

Every array entry is even. An odd target can never match, so the candidate interval eventually becomes empty and the algorithm reports not found.

Why is one row no longer moving?

That search has already finished. Stepping continues the other algorithm so their total comparison costs can be compared.