Trying to implement a recursive binary search in Python. However, facing error with the division command

General Discussions
1

I’m trying to implement a recursive binary search in Python. I have a list with numbers from 0 to 9:

mylist = list(range(10))

However, I’m encountering an error with the division command when trying to calculate the midpoint. Here’s my current code:

def binary_search(mylist, element, low, high):
    low = 0
    high = len(mylist)
    mid = low + (high - mymin) / 2
    if mid == len(mylist):
        return False
    elif mylist[mid] == element:
        return mid
    elif high == low:
        return False
    elif mylist[mid] < element:
        return binary_search(mylist, element, mymin, mid - 1)
    elif mylist[mid] < element:
        return binary_search(mylist, element, mid + 1, mymax)
    else:
        return mid

There are a couple of issues here:

  1. The calculation of mid is incorrect (due to a typo in mymin instead of low).
  2. I need to return True instead of just mid if the element is found.

How can I fix this and also return True instead of mid in some cases?

2

The main issue is the typo with mymin, which should be low. Also, ensure the calculation of mid uses integer division and fix the base cases for correct termination.

def binary_search(mylist, element, low, high):
    if low > high:
        return False  # Element not found
    mid = (low + high) // 2  # Integer division for correct midpoint calculation
    if mylist[mid] == element:
        return True  # Element found
    elif mylist[mid] < element:
        return binary_search(mylist, element, mid + 1, high)
    else:
        return binary_search(mylist, element, low, mid - 1)

In this version, mid is calculated properly, and it returns True when the element is found.

3

Another approach is to simplify the return logic, and use proper boundary checks to avoid incorrect calculations.

def binary_search(mylist, element, low, high):
    if low > high:
        return False
    mid = (low + high) // 2
    if mylist[mid] == element:
        return True
    elif mylist[mid] < element:
        return binary_search(mylist, element, mid + 1, high)
    else:
        return binary_search(mylist, element, low, mid - 1)

This solution is similar but keeps the base case clear and ensures proper division for integer calculation of mid.

4

For better clarity, this solution also uses integer division and provides more information about the recursion process, such as indicating where the element is being searched.

def binary_search(mylist, element, low, high):
    if low > high:
        return False  # Element not found
    mid = (low + high) // 2
    print(f"Searching between indexes {low} and {high}, mid: {mid}")
    if mylist[mid] == element:
        return True  # Element found
    elif mylist[mid] < element:
        return binary_search(mylist, element, mid + 1, high)
    else:
        return binary_search(mylist, element, low, mid - 1)

This solution adds a print statement to indicate the indexes being searched during each recursion.