typestar

Binary search in Python

The fastest way to find a value in sorted data - O(log n) beats scanning.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

How it works

  1. Keeps lo and hi pointers around the region still in play.
  2. Checks the middle element each pass.
  3. Halves the search space until the target is found or the region is empty.

Keywords and builtins used here

The run, in numbers

Lines
11
Characters to type
199
Tokens
69
Three-star pace
100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 41 seconds.

Type this snippet

Step 2 of 5 in Algorithms, step 52 of 72 in Language basics.

← Previous Next →

Binary search in other languages