Algorithms · Searching

Binary Search

The idea

Think of finding a word in a dictionary. Nobody reads page 1, then page 2, then page 3. You open it near the middle, see whether your word comes earlier or later, and instantly ignore half the book. A few splits later you are on the right page.

The problem

Finding a value by checking every item works, but it is painfully slow on big lists. If the list is SORTED, there is a far smarter way: look in the middle, decide which half the target must be in, and throw the other half away. Repeat. Every look removes half of the remaining items.

Why it's slow

Slow? Quite the opposite — this is the fast one. Our demo found the target in ONE comparison where linear search needed five. Each comparison halves what is left: 1,000 items need about 10 looks, a million about 20, a billion about 30. That growth is O(log n). The price of admission: the list must already be sorted.

Pseudocode

  1. make sure the list is sorted first
    Explain this line

    Binary search is USELESS on an unsorted list — this rule is sacred.

  2. put one finger at each end: low and high
    Explain this line

    low and high fence off where the target can still hide.

  3. look at the middle position between them
    Explain this line

    The midpoint between the fingers is always the next guess.

  4. compare the middle item with the target
    Explain this line

    One comparison per guess — watch how few we need.

  5. hit? done. Too small? go right. Too big? go left
    Explain this line

    Each wrong guess still throws away half of the possibilities.

Complexity

Best Average Worst Space
O(1) O(log n) O(log n) O(1)

The classic trade: pay once to keep data sorted, then every search is astonishingly cheap. This is why databases keep indexes.

Code

python 
def binary_search(a, target):  # a must be sorted
    low, high = 0, len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
java 
int binarySearch(int[] a, int target) { // a must be sorted
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
cpp 
int binarySearch(const std::vector<int>& a, int target) {
    int low = 0, high = static_cast<int>(a.size()) - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
javascript 
function binarySearch(a, target) { // a must be sorted
  let low = 0, high = a.length - 1;
  while (low <= high) {
    const mid = (low + high) >> 1;
    if (a[mid] === target) return mid;
    if (a[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
dart 
int binarySearch(List<int> a, int target) { // a must be sorted
  var low = 0, high = a.length - 1;
  while (low <= high) {
    final mid = (low + high) ~/ 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Quick check