接受并查找键数组（而不是单个键）的递归二进制搜索函数

Question

我需要让我的二进制搜索功能搜索多个键，而不是像我现在那样只搜索一个键。如果找到键 return 键的索引，否则 return -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

Answer 1

您可以通过以下方式解决此问题：

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

def binary_search(arr, key):
    """
    Wraps the actual recursive search function, setting initial bounds and
    checking if the key was found or not.
    """
    index = _binary_search(arr, 0, len(arr), key)
    if arr[index] == key:
        return index
    return -1

def vectorised_binary_search(arr, key_arr):
    return [binary_search(arr, key) for key in key_arr]

print(vectorised_binary_search([1, 3, 5, 8, 10], [0, 2, 8, 5]))
print(vectorised_binary_search(range(0, 10, 2), range(10)))

有输出

[-1, -1, 3, 2]
[0, -1, 1, -1, 2, -1, 3, -1, 4, -1]

我冒昧地稍微重写了你的二进制搜索。

Answer 2

你可以试试这个。我写 binary_search 这样它 returns 关键元素的索引，如果找到它 returns -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]

接受并查找键数组（而不是单个键）的递归二进制搜索函数

recursive binary search function that takes in and finds an array of keys (as opposed to a single key)

python

algorithm

recursion

search

binary-search