Editor

Python Program for Binary Search Using Recursion

Intermediate · Recursion

Binary search finds a value in a sorted list by looking at the middle item and then searching only the half that could still contain it. Searching that half is the same problem on a smaller list, so binary search fits recursion naturally. This program prints each step and handles a value that is not in the list.

Program

binary_search_using_recursion.py
def binary_search(numbers, target, low, high):
# Base case 1: the range is empty, so the target is not in the list
if low > high:
return -1
mid = (low + high) // 2
print(f" Searching indexes {low} to {high}, middle value {numbers[mid]}")
# Base case 2: the middle value is the target
if numbers[mid] == target:
return mid
# Recursive step: search only the half that can hold the target
if target < numbers[mid]:
return binary_search(numbers, target, low, mid - 1)
return binary_search(numbers, target, mid + 1, high)
numbers = [5, 12, 19, 27, 34, 46, 58, 63, 71, 88] # must be sorted
for target in [58, 30]: # or: target = int(input("Number to find: "))
print("Looking for", target)
index = binary_search(numbers, target, 0, len(numbers) - 1)
if index == -1:
print(f" {target} is not in the list")
else:
print(f" {target} found at index {index}")
Output
Looking for 58
  Searching indexes 0 to 9, middle value 34
  Searching indexes 5 to 9, middle value 63
  Searching indexes 5 to 6, middle value 46
  Searching indexes 6 to 6, middle value 58
  58 found at index 6
Looking for 30
  Searching indexes 0 to 9, middle value 34
  Searching indexes 0 to 3, middle value 12
  Searching indexes 2 to 3, middle value 19
  Searching indexes 3 to 3, middle value 27
  30 is not in the list

How it works

  1. low and high are the first and last index of the part of the list still being searched, and the first call passes the whole list, 0 to len(numbers) - 1.
  2. There are two base cases: low > high means nothing is left to search, so the function returns -1, and finding the target at mid returns its index.
  3. Otherwise the recursive step searches one half, low to mid - 1 when the target is smaller than the middle value, or mid + 1 to high when it is bigger.
  4. Each call halves the range, so even a list of 1,000 items needs at most about 10 calls.
  5. The list must be sorted, or throwing away half of it could throw away the target.

Other ways to write it

With default arguments

With default arguments
def binary_search(numbers, target, low=0, high=None):
if high is None: # first call: search the whole list
high = len(numbers) - 1
if low > high:
return -1
mid = (low + high) // 2
if numbers[mid] == target:
return mid
if target < numbers[mid]:
return binary_search(numbers, target, low, mid - 1)
return binary_search(numbers, target, mid + 1, high)
numbers = [5, 12, 19, 27, 34, 46, 58, 63, 71, 88]
print("Index of 71:", binary_search(numbers, 71))
print("Index of 5:", binary_search(numbers, 5))
print("Index of 100:", binary_search(numbers, 100), "(not found)")
Output
Index of 71: 8
Index of 5: 0
Index of 100: -1 (not found)

Default values for low and high let the caller write just binary_search(numbers, 71), and the function fills in the whole range on the first call.

Using slicing

Using slicing
def contains(numbers, target):
if len(numbers) == 0: # base case: empty list
return False
mid = len(numbers) // 2
if numbers[mid] == target:
return True
if target < numbers[mid]:
return contains(numbers[:mid], target)
return contains(numbers[mid + 1:], target)
numbers = [5, 12, 19, 27, 34, 46, 58, 63, 71, 88]
for target in [27, 50]:
print(target, "in the list:", contains(numbers, target))
Output
27 in the list: True
50 in the list: False

Passing a slice is simpler to read, but each slice is a copy and its positions do not match the original list, so this version only says whether the value is there.

Try it yourself

Add a calls parameter that goes up by 1 on each call, and print how many calls it takes to find 88 and to give up on 100.

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