P-5.4 Searching and Binary Search

Work through these

• Linear search, and when it is genuinely the right answer

  For small collections, unsorted data, or a single lookup, scanning is faster than any preparation you could do first. Sorting in order to search once is usually a loss.

• Binary search, and getting the boundaries right

  Halving the remaining range each step needs a sorted input and exact care about whether each end is included. Deciding your convention before writing the loop prevents most of the classic mistakes.

  MIT OpenCourseWare 6.006: Introduction to Algorithms · Course

• Finding the first item that satisfies a condition

  The more useful form does not look for an exact value but for the boundary where a condition starts holding. This variant answers far more real questions than exact-match search does.

• Searching over an answer rather than over an array

  If a candidate answer can be tested as too small or large enough, the range of possible answers can be halved even though no array exists. This is where the technique starts earning its reputation.

• Write it once with no off-by-one errors, and test the edges

  Test an empty input, one element, the first and last positions, and a value that is absent. Those five cases catch nearly every implementation mistake this algorithm invites.