Binary search

O(log n)

Binary search needs a sorted array. It checks the middle element: if it equals the target you're done; if the target is smaller you keep the left half, otherwise the right — halving the search space each step. That gives O(log n), but only because the data is sorted (shown here sorted first).

Array
Edit the input and press Play

How it works

  1. Look at the middle element of the current range.
  2. If it equals the target, you're done.
  3. If the target is smaller, keep the left half; if larger, keep the right half.
  4. Repeat on the half that remains until the range is empty.

Pseudocode

1binarySearch(a, target):            # O(log n) — a is sorted2  lo ← 0; hi ← n-13  while lo ≤ hi:4    mid ← (lo + hi) / 25    if a[mid] = target: return mid6    if a[mid] < target: lo ← mid+17    else: hi ← mid-18  return -1