Searching: Linear & Binary

Linear search checks index 0, then 1, and keeps going until it finds the target or runs out of array. It is O(n), it makes no assumptions, and it is the only option on unsorted data. On average it examines half the array when the value is present, and all of it when the value is absent.

It is not a bad algorithm, it is the correct algorithm for a small or unsorted collection. For twenty items the difference against anything cleverer is unmeasurable, and it works on data you cannot sort, such as a stream you are reading once.

Binary search keeps a window of indexes that could still contain the target, described by lo and hi. It compares the middle element with the target: equal means done, too small means the target must be to the right so lo moves past mid, too large means the target must be to the left so hi moves before mid. Every comparison discards half the remaining window.

Step it in the lab and watch the counter next to the dimmed cells: those elements were ruled out without ever being read. That is the whole trick, and it is only sound because the array is sorted. On unsorted data the comparison tells you nothing about which side to keep, which is why the lab refuses to run rather than returning a wrong answer.

The number of halvings needed to reduce n to 1 is log₂ n. A thousand elements take at most 10 comparisons, a million take 20, a billion take 30. Adding a thousand times more data costs ten more comparisons.

Sorting costs O(n log n), so for a single lookup it is not worth it: one linear scan at O(n) is cheaper than sorting to enable a O(log n) search. The calculation changes when you search repeatedly. Sort once at O(n log n), then answer k queries at O(log n) each, and the total is O(n log n + k log n) against O(k·n) for repeated scanning. By the time k is in the thousands the sorted version wins overwhelmingly.

This is the reasoning behind database indexes. An index is a sorted structure maintained alongside the table precisely so that lookups stop being full scans, and the cost is paid on every write instead. If your workload is one write and one read, an index is a waste; at a thousand reads per write it is the difference between a working product and a broken one.

Binary search is famously easy to get subtly wrong. The first bug is the loop condition: `while (lo < hi)` skips the case where the window has narrowed to one element, so a target sitting there is reported missing. With inclusive bounds the condition must be `lo <= hi`.

The second is the update. Writing `hi = mid` instead of `hi = mid - 1` leaves the already-rejected middle element inside the window, and when lo and hi meet on it the loop stops making progress and spins forever. Because mid has just been compared and rejected, both updates must step past it: `lo = mid + 1` or `hi = mid - 1`.

There is a third, historical bug worth knowing: computing the midpoint as `(lo + hi) / 2` can overflow a fixed-size integer on very large arrays, which is why languages with fixed-width integers use `lo + (hi - lo) / 2`. JavaScript numbers make this harmless in practice, but the same code in Java or C is a real defect.