时间戳

首页 > 解决方案 > 递归二分查找，通过切片进行分类

python - 递归二分查找，通过切片进行分类

问题描述

我正在尝试使用递归在整数列表上实现二进制搜索，并通过每次对列表进行切片来“消除”一半的项目。我写了一些，如果达到目标值，我有点卡在我应该返回“True”的部分。迭代地，我会检查“左”是否大于“右”，但我想让函数的参数尽可能简单。

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)

标签： pythonrecursionbinary-search

解决方案

False如果找不到该值，则返回以下内容；否则返回索引。二分查找递归执行。

代码的关键补充是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

推荐阅读