5 Effective Ways to Implement Binary Search with Recursion in Python

Rate this post

πŸ’‘ Problem Formulation: Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed the possible locations to just one. For a list arr with elements sorted in ascending order, and a target value target, we wish to find the index of target in arr, or -1 if it does not exist. The input might be arr = [1, 3, 5, 7, 9] and target = 5, with the desired output being 2, the index of the target value in the array.

Method 1: Standard Recursion

This method involves writing a recursive binary search function that takes the array, target, and the current search boundaries as arguments. The search boundaries are updated with each recursive call until the target is found or the search space is empty.

Here’s an example:

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

arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search_rec(arr, target, 0, len(arr)-1))

Output:

2

This code defines a function binary_search_rec that performs a binary search using recursion. The function is initially called with the full range of the array. Depending on the comparison between the middle element and the target, the function calls itself with either the left half or the right half of the array, or returns the middle index if the target is found.

Method 2: Recursion with Python Slicing

Python’s list slicing can be used to simplify the recursive binary search function by eliminating the need for explicit boundary parameters. This approach is less efficient due to the additional memory used by slicing, but it is more concise.

Here’s an example:

def binary_search_rec_slice(arr, target):
    if len(arr) == 0:
        return -1
    mid = len(arr) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_rec_slice(arr[:mid], target)
    else:
        result = binary_search_rec_slice(arr[mid+1:], target)
        return mid + 1 + result if result != -1 else -1

arr = [1, 3, 5, 7, 9]
target = 7
print(binary_search_rec_slice(arr, target))

Output:

3

In this snippet, binary_search_rec_slice uses Python list slicing to pass sub-arrays to recursive calls. On each call, it checks if the array is empty for the base case, or if the middle element is the target. When searching the right sub-array, the function adjusts the returned index to match the original array.

Method 3: Tail Recursion Optimization

In languages that support tail call optimization, this version of the binary search would be preferred, as it can be optimized by the compiler to prevent stack overflow. Python does not officially support tail call optimization, but this method can still be illustrative for understanding the concept.

Here’s an example:

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

arr = [1, 3, 5, 7, 9]
target = 3
print(binary_search_tail_rec(arr, target, 0, len(arr)-1))

Output:

1

The binary_search_tail_rec function is a tail-recursive version of the binary search algorithm. Each recursive call is the last operation in the function, which is the requirement for tail recursion. However, Python does not optimize tail recursion, so this might not offer performance benefits compared to the standard recursion method.

Bonus One-Liner Method 4: Lambda Function

A fun and concise way to implement binary search is by using a lambda function. This approach condenses the algorithm into a single line at the expense of readability.

Here’s an example:

binary_search_lambda = (lambda f: (lambda x: x(x)) (lambda y: f(lambda *args: y(y)(*args))))(lambda bs: lambda arr, target, low, high: -1 if low > high else ((low+high)//2 if (mid := (low + high) // 2) == target else bs(arr, target, low, mid-1) if arr[mid] > target else bs(arr, target, mid+1, high)))

arr = [1, 3, 5, 7, 9]
target = 9
print(binary_search_lambda(arr, target, 0, len(arr)-1))

Output:

4

The one-liner binary_search_lambda uses a fixed-point combinator (Y-combinator) to enable recursion in a lambda function. It is a clever yet impractical approach for daily use due to its complexity and lack of readability.

Summary/Discussion

  • Method 1: Standard Recursion. It is clear and maintains a good balance between performance and readability. The downside is that it requires the management of low and high indices.
  • Method 2: Recursion with Python Slicing. It offers a concise code but at the cost of performance due to increased memory use. It simplifies boundary management by using slicing instead.
  • Method 3: Tail Recursion Optimization. This approach is mainly theoretical in the context of Python, as Python does not optimize tail recursion. It is most useful as an academic exercise.
  • Method 4: Lambda Function. The one-liner method is a powerful demonstration of Python lambda capabilities but lacks practicality for use in real-world applications due to its complex and unreadable nature.