← All lessons

Binary search

Sign in · Sign up

Lesson 12.2

If the list is sorted, you can search twice as fast: look at the middle and throw away half.

def binary_search(numbers, target):
    left, right = 0, len(numbers) - 1

    while left <= right:
        mid = (left + right) // 2
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            left = ...            # the right half
        else:
            right = ...           # the left half

    return -1
  • left and right are the bounds of the piece where the answer may still be;
  • // is whole division: an index is never a decimal;
  • left = mid + 1 and right = mid - 1 throw away a half; without the +1 and -1 the loop would never end;
  • on an unsorted list this works incorrectly — sorting is required.

The check gives a sorted list numbers and the number target. Write binary_search and print the index it finds, or -1.

Hint

Keep two bounds of the piece where the answer may still be, and halve it.

The middle is (left + right) // 2: whole division, an index is never a decimal. The bounds must move by mid + 1 and mid - 1, otherwise the loop never ends. The loop runs while left <= right.