Recursive binary search in Python

Binary search finds an item in a sorted list. It checks the middle item. If that is not the target, it searches only the half where the target must be, and repeats.

The program

python

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1                      # the range is empty: not found

    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

numbers = [3, 8, 15, 21, 34, 42, 57, 63, 78]
print(binary_search(numbers, 42))
print(binary_search(numbers, 3))
print(binary_search(numbers, 50))
print(binary_search([], 7))

output

5
0
-1
-1

How it works

low and high are the first and last positions still being searched. At the start they cover the whole list.
If the middle item is smaller than the target, the target can only be to the right, so the next call searches from mid + 1. If it is larger, the next call searches up to mid - 1.
When low passes high, nothing is left to search, so the function returns -1.
Each step halves the list. A list of 1,000,000 items needs at most 20 checks. A loop that checks every item could need 1,000,000.
The list must be sorted. On an unsorted list the result is wrong, and there is no error to warn you.

Another way: a loop and bisect

The same search as a while loop, and with the standard library bisect module:

python

import bisect

def binary_search_loop(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [3, 8, 15, 21, 34, 42, 57, 63, 78]
print(binary_search_loop(numbers, 63))

i = bisect.bisect_left(numbers, 63)
print(i if i < len(numbers) and numbers[i] == 63 else -1)

output

7
7

bisect_left returns the position where the target would be inserted to keep the list sorted. If the item at that position equals the target, the target is in the list.

Related programs: Linear search.

Binary search in Python (recursive)

The program

How it works

Another way: a loop and bisect