The Runtime Theory
mediumRuntimeDSA#complexity#memory-access

Why Can Binary Search Be Slower Than a Linear Scan?

A TRT practice prompt about asymptotic growth, memory locality, branch behavior, and choosing an algorithm for a real workload.

TRT practice prompt — not a verified question from a named employer.

The Runtime Theory Team1 min read

A strong answer

Binary search uses O(log n) comparisons on sorted random-access data, while a linear scan can use O(n). For large arrays, the asymptotic difference usually matters. For small arrays, a scan may still win because its loop is simple, accesses neighboring memory, and can be easy for the processor to prefetch and vectorize. Binary search jumps among positions and has data-dependent branches.

The crossover depends on the language, element comparison, data size, cache state, and implementation. I would benchmark representative data with repeated runs, guard against compiler elimination, and report the target hardware and compiler settings. I would not claim a universal threshold.

I would also confirm that the input is sorted and define how duplicates should be handled. If I need the first equal value, I would use a lower-bound invariant rather than stop at any match.

Follow-up direction

Explain why the benchmark's input distribution and cache state resemble the actual workload, then compare branch and memory behavior if profiling tools are available.

This answer walks

Practice follow-ups

  1. 01What input property does binary search require?
  2. 02How would you measure the crossover point for a particular machine?
  3. 03How do duplicates change a search implementation's contract?

More interviews in this topic

One dispatch a week

The trace behind each question, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save