Python中的递归二分查找 [英] Recursion binary search in Python

问题描述

我有一个包含 0-9 数字的列表:

I have a list with numbers from 0-9:

mylist = list(range(10))

我在获取 mid 的除法命令中遇到错误:

I am getting an error with the division command to get mid:

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

如果我想返回 True 我将如何在 return binary_search(mylist, element, mymin, mid-1) 之上写它?

and if I wanted to return True how would I write that on top of return binary_search(mylist, element, mymin, mid-1)?

推荐答案

递归解决方案:

def binary_search_recursive(arr, elem, start=0, end=None):
    if end is None:
        end = len(arr) - 1
    if start > end:
        return False

    mid = (start + end) // 2
    if elem == arr[mid]:
        return mid
    if elem < arr[mid]:
        return binary_search_recursive(arr, elem, start, mid-1)
    # elem > arr[mid]
    return binary_search_recursive(arr, elem, mid+1, end)

迭代解决方案:

def binary_search_iterative(arr, elem):
    start, end = 0, (len(arr) - 1)
    while start <= end:
        mid = (start + end) // 2
        if elem == arr[mid]:
            return mid
        if elem < arr[mid]:
            end = mid - 1
        else:  # elem > arr[mid]
            start = mid + 1

    return False

这篇关于Python中的递归二分查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！