рекурсивная функция двоичного поиска, которая принимает и находит массив ключей (в отличие от одного ключа)

Question

Мне нужно, чтобы моя функция бинарного поиска искала несколько ключей, а не только тот, который у меня есть в настоящее время. Если ключ найден, верните индекс ключа, иначе верните -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

Вы можете попробовать это. Я написал 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)

---

output

[-1, -1, 3, 2]

Answer 2

Вот способ, которым вы могли бы go об этом:

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]

Я позволил себе немного переписать ваш бинарный поиск .