递归二进制搜索，通过切片进行二分法

Question

我正在尝试使用递归对整数列表执行二分搜索，并通过每次对列表进行切片来“消除”一半的项目。我写了一些，但我有点卡在我应该 return “True” 如果达到目标值的部分。我会反复检查 'left' 是否大于 'right'，但我希望函数的参数尽可能简单。

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)

Answer 1

下面returns False如果找不到值；否则它 returns 索引。二分查找递归执行。

您的代码的关键添加是 return您的函数调用。我添加了一些 return a+b if a != False else a 逻辑，以在值不在可迭代对象中时处理返回 False。

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

递归二进制搜索，通过切片进行二分法

recursive binary search, biesction by slicing

python

recursion

binary-search