Editor

Python Program for Binary Search

Intermediate · Searching and sorting

Binary search finds a value in a sorted list by checking the middle item and throwing away the half that cannot contain the target. Each step halves the part left to search, so even a list of a million numbers needs only about 20 checks. This program prints each step and reports when a number is not in the list.

Program

binary_search.py
def binary_search(numbers, target):
low = 0
high = len(numbers) - 1
while low <= high:
mid = (low + high) // 2
print(f" Checking index {mid}, value {numbers[mid]}")
if numbers[mid] == target:
return mid
elif numbers[mid] < target:
low = mid + 1 # the target can only be in the right half
else:
high = mid - 1 # the target can only be in the left half
return -1 # not found
numbers = [3, 8, 15, 23, 42, 57, 71] # must already be sorted
targets = [42, 50] # or: targets = [int(input("Enter a number to find: "))]
for target in targets:
print("Searching for", target, "in", numbers)
index = binary_search(numbers, target)
if index == -1:
print(f" {target} is not in the list")
else:
print(f" {target} found at index {index}")
Output
Searching for 42 in [3, 8, 15, 23, 42, 57, 71]
  Checking index 3, value 23
  Checking index 5, value 57
  Checking index 4, value 42
  42 found at index 4
Searching for 50 in [3, 8, 15, 23, 42, 57, 71]
  Checking index 3, value 23
  Checking index 5, value 57
  Checking index 4, value 42
  50 is not in the list

How it works

  1. The list must be sorted, otherwise throwing away half of it could skip the target.
  2. low and high mark the part of the list still being searched, starting with the whole list.
  3. mid = (low + high) // 2 picks the middle index, and the value there is compared with the target.
  4. If the middle value is smaller, the target can only be to the right, so low moves to mid + 1; if it is larger, high moves to mid - 1.
  5. When low passes high, nothing is left to search, so the function returns -1 to mean not found.

Other ways to write it

Using recursion

Using recursion
def binary_search(numbers, target, low, high):
if low > high:
return -1 # nothing left to search
mid = (low + high) // 2
if numbers[mid] == target:
return mid
if numbers[mid] < target:
return binary_search(numbers, target, mid + 1, high)
return binary_search(numbers, target, low, mid - 1)
numbers = [3, 8, 15, 23, 42, 57, 71]
for target in [57, 10]:
index = binary_search(numbers, target, 0, len(numbers) - 1)
print("Index of", target, "is", index, "(-1 means not found)")
Output
Index of 57 is 5 (-1 means not found)
Index of 10 is -1 (-1 means not found)

Instead of a loop, the function calls itself on the half that can still hold the target.

Using the bisect module

Using the bisect module
import bisect
numbers = [3, 8, 15, 23, 42, 57, 71]
for target in [42, 50]:
i = bisect.bisect_left(numbers, target)
if i < len(numbers) and numbers[i] == target:
print(target, "found at index", i)
else:
print(target, "is not in the list")
Output
42 found at index 4
50 is not in the list

bisect_left() does the binary search and returns where the target is, or where it would go, so the program checks that the value there really matches.

Try it yourself

Count the checks for each search and compare that with how many a simple loop from the start of the list would need.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises