AlgoVerse

Binary search

In a sorted array, compare the middle item of the range with the value you want and throw away half of the range each time.

Binary search only works on a sorted array. The range a[low..high] is where target can still be. In each round, look at the middle item a[mid]:

Read the full explanation ↓
Input:
n=10 · target=9PDF export

Ten sorted numbers; 9 is found after halving the range three times.

  1. def binary_search(a, target):
  2. low = 0
  3. high = len(a) - 1
  4. while low <= high:
  5. mid = (low + high) // 2
  6. if a[mid] == target:
  7. return mid
  8. if a[mid] < target:
  9. low = mid + 1
  10. else:
  11. high = mid - 1
  12. return -1

Invariant: If target is in the array at all, it is in a[low..high].

Start

target 9103142638495116147178209

Local variables

target9

Orange = changed in this step

a list

13468911141720

Call stack

  1. binary_search()line 1
Step 1 of 17
Black = probe · Orange = key stepcompare: 0/5 · probe: 0/3 · go_right: 0/1 · go_left: 0/1 · found: 0/1

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • probe
    • current input (n=10)
    0246846810121416n = number of itemscomparisonsprobe
    Show as a table
    ncomparisonsprobe
    43.62.1
    64.82.7
    84.92.8
    105.12.8
    126.53.6
    1463.3
    165.63.1
    Explanation

    The idea

    Binary search only works on a sorted array. The range a[low..high] is where target can still be. In each round, look at the middle item a[mid]:

    • If it equals target, you are done.
    • If it is smaller, target can only be in the right half: low = mid + 1.
    • If it is larger, only in the left half: high = mid − 1.

    When low > high the range is empty and target is not in the array; the function returns −1.

    Cost

    Each round halves the range, so at most ⌊log₂ n⌋ + 1 rounds are needed: at most 10 for a thousand items, 20 for a million. The extra memory is O(1).

    Why the array must be sorted

    Throwing away half of the range is only correct if every item left of a[mid] is smaller or equal and every item to its right is larger or equal. The input validator does not accept an unsorted array.

    What to watch in the trace

    • The blue band is the range low..high, and the dashed blue line is the height of target.
    • The low, mid and high arrows move under the bars; watch the range halve every round.
    • The "target repeats" input shows that this version does not necessarily find the first copy.