Python Program to Find Binary Search Using Recursion

You can perform binary search using recursion in Python by defining a function that takes the list, the target value, and the current low and high indices, then recursively checks the middle element with def binary_search(arr, target, low, high): and returns the index if found or -1 if not.

Examples

Input[1, 2, 3, 4, 5], target=3

Output2

Input[10, 20, 30, 40, 50], target=25

Output-1

Input[5], target=5

Output0

How to Think About It

To find an element using binary search recursively, start by checking the middle element of the list. If it matches the target, return its index. If the target is smaller, search the left half; if larger, search the right half. Repeat this process by calling the function again with updated boundaries until the element is found or the search space is empty.

Algorithm

1

Start with low index as 0 and high index as length of list minus one.

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 than the middle element, recursively search the right half.

6

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

Code

python

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

# Example usage
arr = [1, 2, 3, 4, 5]
target = 3
result = binary_search(arr, target, 0, len(arr) - 1)
print(result)

Output

2

Dry Run

Let's trace the search for target 3 in the list [1, 2, 3, 4, 5] through the code

1

Initial call

low=0, high=4, mid=(0+4)//2=2, arr[mid]=3

2

Check middle element

arr[mid] == target (3 == 3), return mid=2

Call	low	high	mid	arr[mid]	Action
1	0	4	2	3	Found target, return 2

Why This Works

Step 1: Divide the list

The function splits the list into halves by calculating the middle index with mid = (low + high) // 2.

Step 2: Compare middle element

It compares the middle element with the target using arr[mid] == target to check if the search is successful.

Step 3: Recursive search

If not found, it calls itself recursively on the left or right half depending on whether the target is smaller or larger than the middle element.

Step 4: Base case

When the search space is empty (low > high), it returns -1 indicating the target is not in the list.

Alternative Approaches

Iterative binary search

python

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

# Example usage
arr = [1, 2, 3, 4, 5]
target = 3
print(binary_search_iterative(arr, target))

This method uses a loop instead of recursion, which can be more memory efficient because it avoids function call overhead.

Using Python's bisect module

python

import bisect

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

# Example usage
arr = [1, 2, 3, 4, 5]
target = 3
print(binary_search_bisect(arr, target))

This uses Python's built-in module for binary search, which is optimized and simple but less educational about recursion.

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

Time Complexity

Binary search divides the search space in half each time, so it runs in logarithmic time, O(log n), where n is the number of elements.

Space Complexity

The recursive approach uses O(log n) space due to the call stack from recursive calls. The iterative approach uses O(1) space.

Which Approach is Fastest?

Both recursive and iterative binary search have the same time complexity, but iterative is more memory efficient. Using Python's bisect module is often fastest in practice due to optimization.

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 practical use
Python bisect Module	O(log n)	O(1)	Fast, built-in, and simple usage