Searching: linear and binary search

To find one name in a sorted list of a million, binary search never needs more than 20 checks.

Looking for one value

Searching is the problem of finding where a value is in a collection, or learning that it is not there. Your phone does it when you type a contact's name, a shop does it when it checks whether an item is in stock, and a spell checker does it for every word you type. The input is a list and a target value. The output is the position of the target, or a sign such as -1 meaning "not found".

Linear search: one at a time

The plainest method is to start at the left and check each value in turn until you find the target or run out of list. This is linear search. It works on any list, sorted or not. Its cost depends on luck: if the target is first, one check is enough; if it is last or missing, you check every value. For a list of n values the worst case is n checks. A list twice as long can take twice as many checks, which is where the name "linear" comes from: the work grows in a straight line with the size.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // found it
  }
  return -1;                             // checked everything
}

Binary search: halve what is left

If the list is sorted, you can do much better. Think of the number guessing game: someone picks a number from 1 to 100 and answers only "higher" or "lower". A sensible player guesses 50 first. Whatever the answer, half the possibilities are gone. The next guess is the middle of what is left, and so on. Binary search does exactly this with a sorted list. It keeps two markers, lo and hi, around the part where the target could still be. It checks the middle value. If that is the target, it is done. If the middle value is smaller than the target, everything to its left is smaller too, so lo moves past the middle. If it is larger, hi moves before the middle. When lo passes hi, nothing is left and the target is not in the list.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // target is to the right
    else hi = mid - 1;                     // target is to the left
  }
  return -1;
}

How many checks?

Each check of binary search at least halves the part that is left. Starting from n values, after one check at most about n/2 remain, after two about n/4, and so on until one value is left. The number of halvings needed to get from n down to 1 is the base 2 logarithm of n, written log₂ n. Counting the final check as well, binary search needs at most ⌊log₂ n⌋ + 1 checks, where ⌊ ⌋ means rounding down. For 100 values that is 7 checks, which is why the guessing game can always be won in 7 guesses. For 1,000 values it is 10, for a million 20, and for a billion 30.

The catch: the list must be sorted

Binary search only works because, in a sorted list, one comparison tells you which side the target must be on. On an unsorted list the middle value tells you nothing about its neighbours, so you are back to linear search. Sorting takes work of its own (the next two units are about that), so the choice depends on use. If you search a list once, a linear search may be cheapest. If you search the same list thousands of times, sorting it once and then using binary search pays off quickly. This trade between preparing data and answering questions about it runs through the whole subject.