时间戳

首页 > 解决方案 > 递归二分搜索函数，它接收并找到一个键数组（而不是单个键）

python - 递归二分搜索函数，它接收并找到一个键数组（而不是单个键）

问题描述

我需要让我的二进制搜索功能搜索多个键，而不仅仅是我目前拥有的一个。如果找到键返回键的索引，否则返回-1。

例子： 

array = [ 1, 3, 5, 8, 10]
keys = [ 0, 2, 8, 5]

answer = [ -1, -1, 3, 2]

帮助将不胜感激！

def biSearch(A, low, high, key):

    mid = (high + low) // 2

    if low >= high: 
        return mid

    elif A[mid] >= key:        # we are in the left half of the array
        index = biSearch(A, low, mid, key)
        return index

    else:                   # we are in the right half of array
        index = biSearch(A, mid + 1 , high, key)
    return index


def search(A, key):
    low = 0
    high = len(A)
    index = biSearch(A, low, high, key)

    return index

标签： pythonalgorithmrecursionsearchbinary-search

解决方案

你可以试试这个。我binary_search这样写，如果找到它返回它返回的关键元素的索引-1。

def binary_search(a,key,low,high):

    if high >=low:
        mid=low +(high-low)//2
        if key == a[mid]:
            return mid
        elif key < a[mid]:
            return binary_search(a,key,low,mid-1)
        else:
            return binary_search(a,key,mid+1,high)
    else :
        return -1

a= [ 1, 3, 5, 8, 10]
Keys=[0, 2, 8, 5]
out=[binary_search(a,idx,0,len(a)-1) for idx in Keys]
print(out)

输出

[-1, -1, 3, 2]

推荐阅读