A strong answer
Binary search does O(log n) comparisons and a linear scan does O(n), so for large arrays binary search wins by orders of magnitude. For small arrays, roughly up to a few dozen to a few hundred elements depending on the element size and the machine, a scan can win, because of costs Big-O ignores.
A scan reads consecutive memory: one cache line serves several elements, the hardware prefetcher fetches ahead, and the compiler can vectorize the comparisons, checking 8 or 16 elements per instruction. Its loop branch is predictable, taken every time until the end. Binary search jumps around: each probe can touch a new cache line, the probes depend on each other so their misses can't overlap, and the "go left or right" branch is essentially random, so the processor mispredicts it about half the time, costing 10 to 20 cycles each.
That is why real code often mixes the two: B-tree nodes holding dozens of keys are commonly searched linearly or with vector instructions, and some binary search implementations switch to a scan once the range is small. Branchless binary search replaces the branch with a conditional move, and layouts such as Eytzinger (storing the array in breadth-first order of the implicit search tree) put the elements probed early next to each other so they share cache lines and can be prefetched.
To decide for a specific case, I would benchmark both on realistic sizes and data, with the cache in a realistic state, and report the crossover for that machine rather than quoting a universal threshold.
What the interviewer is listening for
- Agreement that Big-O decides for large n, and a clear account of what changes for small n.
- Cache lines, prefetching, branch misprediction and vectorization as the specific reasons.
- How real systems combine the two, and how to measure.
Common mistakes
- Saying binary search is always faster because O(log n) is smaller.
- Quoting one universal crossover size.
- Forgetting that binary search requires sorted input, which may cost more than the scan.