Python Program for Binary Search Using Recursion

A Python program for binary search using recursion defines a function like def binary_search(arr, low, high, x): that checks the middle element and recursively searches the left or right half until the element is found or the range is empty.

Examples

Inputarr = [1, 3, 5, 7, 9], x = 7

Output3

Inputarr = [2, 4, 6, 8, 10], x = 5

Output-1

Inputarr = [10], x = 10

Output0

How to Think About It

To do a binary search with recursion, first find the middle of the list. If the middle value is the one you want, return its position. If the value is smaller, search the left half by calling the function again with the left side range. If larger, search the right half similarly. Stop when the range is empty.

Algorithm

1

Start with the full list range from low to high indexes.

2

Find the middle index between low and high.

3

If the middle element equals the target, return the middle index.

4

If the target is less than the middle element, recursively search the left half.

5

If the target is greater, recursively search the right half.

6

If low exceeds high, return -1 to show the target is not found.

Code

python

def binary_search(arr, low, high, x):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == x:
        return mid
    elif x < arr[mid]:
        return binary_search(arr, low, mid - 1, x)
    else:
        return binary_search(arr, mid + 1, high, x)

arr = [1, 3, 5, 7, 9]
x = 7
result = binary_search(arr, 0, len(arr) - 1, x)
print(result)

Output

3

Dry Run

Let's trace searching for 7 in [1, 3, 5, 7, 9] using recursion.

1

Initial call

low=0, high=4, mid=2, arr[mid]=5, x=7

2

Search right half

x > arr[mid], call binary_search(arr, 3, 4, 7)

3

Second call

low=3, high=4, mid=3, arr[mid]=7, x=7

4

Found element

arr[mid] == x, return 3

Call	low	high	mid	arr[mid]	x	Action
1	0	4	2	5	7	x > arr[mid], search right half
2	3	4	3	7	7	Found element, return index 3

Why This Works

Step 1: Divide the list

The code finds the middle index with mid = (low + high) // 2 to split the list into two halves.

Step 2: Compare middle element

It compares arr[mid] with the target x to decide if the search is done or which half to search next.

Step 3: Recursive calls

If the target is not found, the function calls itself with updated low and high to search the correct half, narrowing the search range.

Alternative Approaches

Iterative binary search

python

def binary_search_iter(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif x < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

arr = [1, 3, 5, 7, 9]
x = 7
print(binary_search_iter(arr, x))

Uses a loop instead of recursion, which can be more memory efficient for large lists.

Using Python's bisect module

python

import bisect

def binary_search_bisect(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    return -1

arr = [1, 3, 5, 7, 9]
x = 7
print(binary_search_bisect(arr, x))

Uses built-in module for binary search, simpler but less educational about recursion.

Complexity: O(log n) time, O(log n) space

Time Complexity

Binary search divides the list in half each step, so it takes about log base 2 of n steps to find the element or conclude it's missing.

Space Complexity

Recursive calls add to the call stack, so space used is proportional to the recursion depth, which is O(log n).

Which Approach is Fastest?

Iterative binary search uses O(1) space and is faster in practice due to no recursion overhead, but recursive is easier to understand.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Learning recursion and divide-and-conquer
Iterative binary search	O(log n)	O(1)	Memory efficient and fast in production
bisect module	O(log n)	O(1)	Quick built-in solution for sorted lists