recursive binary search, biesction by slicing-CodePudding

I'm trying to implement a binary search on a list of integers using recursion and "eliminating" half of the items by slicing the list each time. I wrote some of it and I'm kind of stuck in the part where I'm supposed to return "True" if the target value is met. Iteratively I'd check if 'left' is greater than 'right' but I want to keep the functions' arguments as simple as possible.

def binary_search(iterable, target):

    left_index = 0
    right_index = len(iterable)
    mid = (left_index   right_index) // 2

    if iterable[mid] == target:
        return True
    elif iterable[mid] < target:
        iterable = iterable[mid:right_index]
        print(iterable)
        binary_search(iterable,target)
    elif iterable[mid] > target:
        iterable = iterable[left_index:mid]
        print(iterable)
        binary_search(iterable,target)

CodePudding user response：

The below returns False if the value is not found; otherwise it returns the index. The binary search executes recursively.

The key addition to your code is returning your function calls. I added some return a b if a != False else a logic, to handle returning False if the value isn't in the iterable.

def binary_search(iterable, target):
    # if the list is down to one element, and it isn't the target, return False
    if len(iterable) == 1 and iterable[0] != target: return False
        
    left_index = 0
    right_index = len(iterable)
    mid = (left_index   right_index) // 2

    if iterable[mid] == target:
        return mid
    elif iterable[mid] < target:
        iterable = iterable[mid:right_index]
        v = binary_search(iterable,target)
        # if v is not False, add it to the left side of the window and return
        # else return False
        return v   mid if v != False else v
    elif iterable[mid] > target:
        iterable = iterable[left_index:mid]
        v = binary_search(iterable,target)
        return v   left_index if v != False else v