Нахождение среднего значения индекса массива в алгоритме бинарного поиска в Python

Question

Я новичок в Python и реализую алгоритм двоичного поиска.Вот алгоритм:

def binary_search(list, item):
    low = 0     
    high = len(list)-1

    while low <= high:
        mid = (low + high)
        guess = list[mid]

        if guess == item:
            return mid      
        if guess > item:
            high = mid - 1      
        else:
            low = mid + 1   
    return None

Мой вопрос касается линии mid = (low + high).Алгоритм возвращает правильное местоположение индекса для любого элемента в массиве, использую ли я mid = (low + high) или mid = (low + high)/2.Это почему?Я искал повсюду объяснение этого конкретного вопроса и не могу его найти.Все, что я обнаружил, это то, что Python 3 автоматически округляет числа, которые не делятся равномерно, поэтому для массива с нечетным числом элементов, например 13, индекс среднего элемента будет равен 6. Но как алгоритм, приведенный выше, получитк среднему элементу индекса без деления на 2 каждый раз?

Answer 1

Это потому, что ваш алгоритм не является двоичным поиском.

mid = (low + high)

Так как высокий начинается с len(arr) - 1, а низкий всегда начинается с 0 средний всегда начинается с len(arr) - 1.

if guess > item:
    high = mid - 1

В этом случае при следующем пересчете mid значение mid уменьшается на единицу.Так что, если предположение слишком велико, оно падает на один элементДело в том, что mid всегда начинается с len(arr) - 1, это всегда будет True.guess всегда будет начинаться как самый большой элемент, а затем понижаться один за другим.Пока вы не нажмете:

if guess == item:
    return mid

В этом случае вы просто возвращаете предмет.Ваш алгоритм ищет элемент линейно от последнего элемента до первого по одному.

Если вы на самом деле добавите print(low, high, mid), вы получите такой вывод:

0 6 6
0 5 5
0 4 4
0 3 3
0 2 2
0 1 1
0 0 0