Searching Algorithms

Finding an element

Searching answers one question: "is this value here, and where?" The algorithm you can use depends entirely on whether your data is sorted.

Linear search — O(n)

Linear search walks the collection element by element until it finds the target. It works on any data, sorted or not.

for (int i = 0; i < n; i++)
  if (arr[i] == target) return i;
return -1;   // not found

Binary search — O(log n)

If the array is sorted, you can play higher-or-lower. Compare the target to the middle element; if it's smaller, search the left half, otherwise the right half. Each step eliminates half the remaining elements.

int lo = 0, hi = n - 1;
while (lo <= hi) {
  int mid = (lo + hi) / 2;
  if (arr[mid] == target) return mid;
  if (arr[mid] < target) lo = mid + 1;
  else                   hi = mid - 1;
}
return -1;   // not found

This is the single most important insight in introductory algorithms: a million-element sorted array needs only about 20 comparisons. A billion elements needs 30. The growth is logarithmic.

Bugs in binary search are notoriously easy to write. The classic one is integer overflow in (lo + hi) / 2 — use lo + (hi - lo) / 2 instead. A bug of exactly this kind survived in Java's standard library for almost a decade.

When to use which

• Unsorted data, or a single one-off lookup → linear search.
• Sorted data, or many lookups against the same set → binary search.
• Repeated lookups by key → a hash map or set, which gives O(1) average lookup regardless of order.

Binary search as a general technique

Binary search is more than a search routine — it is a general technique for any problem where the answer space is monotonic (if a value works, all values on one side work too). Examples: finding the smallest capacity that ships all packages, the earliest day a condition becomes true, the square root of a number.