Editor

Binary search in Python

Binary search finds a value in a sorted list by checking the middle and throwing away the half that cannot hold it, so every step halves what is left to search.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. The list must be sorted. low and high mark the part of the list that could still hold target.
  2. Look at the middle value, nums[mid]. If it is the target, return mid.
  3. If it is too small, the target can only be to its right, so low = mid + 1. If it is too big, high = mid - 1.
  4. Each step halves the range. When low passes high, the range is empty and the target is not in the list.

What to watch

  • Watch low, mid and high close in on 13 in three steps.
  • Watch the search for 6 end with low just past high: nothing is left to check, so it returns -1.
  • Watch how many bars are never looked at. That is where the O(log n) speed comes from.

The code

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1      # target is in the right half
        else:
            high = mid - 1     # target is in the left half
    return -1

data = [1, 3, 5, 7, 9, 11, 13, 15]
print("Index of 13:", binary_search(data, 13))
print("Index of 6:", binary_search(data, 6))
Output
Index of 13: 6
Index of 6: -1

Open it in the editor · Python Program for Binary Search, explained