где ошибка в бинарном поиске?

Рейтинг: -1Ответов: 1Опубликовано: 27.01.2023
def binary_search(array, item):
    low = 0
    high = len(array) - 1
    while low < high:
        mid = (low + high)//2
        solve = array[mid]
        if solve == item:
            return mid
        if solve > item:
            high = solve - 1
        else:
            low = solve + 1
    return None

haha = [2,3,4,5,12,20,32]
print(binary_search(haha, 12))

Все должно работать правильно, у меня отсортированный массив, число 3,4,5 из массива алгоритм находит, но почему при поиске 12,20,32 пишет что таких чисел в массиве нет. Так же первое число массива, если я ставлю low<=high, выписывает ошибку что array[mid] выходит за рамки. Функция простая, при входе даешь массив и число, которое найти надо, при выходе получаешь позицию этого числа в массиве

python python-3.x
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Нужно поменять переменную с solve на mid при вычислении low и high, а также заменить < на <= в while

def binary_search(array, item):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = (low + high) // 2
        solve = array[mid]
        if solve == item:
            return mid
        if solve > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


haha = [2, 3, 4, 5, 12, 20, 32]
print(binary_search(haha, 12)) # 4