Бинарный поиск. Правильно ли работает?

Question

[Moskaa]

def binarSearch(list, value):
    i = 0
    first = 0
    last = len(list) - 1;
    middle = int((first + last) / 2)

    while value != list[middle]:
        if value < list[middle]:
            last = middle
            middle = int((first + last) / 2)

        elif value > list[middle]:
            first = middle + 1
            middle = int((first + last) / 2)

        if i == middle - 1 or i >= 5 and len(list) <= 4:
            return -1

        i += 1

    return value

Это код бинарного поиска, писал сам. Совсем недавно начал его изучать и мне всегда казалось, что в реализации это очень сложный алгоритм, но я написал его достаточно быстро и понял всю суть. И меня волнует, что это казалось так легко. И у меня вопрос: я правильно написал код? Если да, то можно ли его как-то оптимизировать. Но если нет, то что не так?

Answer 1

[Wataru]

if i == middle - 1 or i >= 5 and len(list) <= 4:
            return -1

Вот эта часть вызвает вопросы. Отладочный код остался?

Проблема в вашем коде, что он виснет, если числа в массиве вообще нет. Условие должно быть не про равенство, а про то, что у вас отрезок пуст (или длины 1) - надо сравнивать first и last.

Обычно middle не поддерживают между итерациями цикла, а просто считают внутри. Между итерациями переходят только first и last.

А так, да, бинпоиск - это весьма простой алгоритм.

Comments

[Moskaa]

Это часть кода нужна в случае, если элемент не найден. Насчёт first, last, middle я думал, что их смысл заключается в другом. Но похоже, что нет. Как я понимаю главная ошибка заключается в том, что на пустом массиве выводится ошибка, но судя по Вашим замечаниям, я постараюсь переписать код и поподробнее ознакомлюсь с теорией.
И насчёт последнего, для меня этот алгоритм сложный. Сортировка пузырьком была намного легче.
Спасибо огромное! Очень сильно выручаете.

Answer 2

[fenrir]

Нет, не правильно.
1) Возвращается значение, вместо индекса
2) На пустом массиве будет ошибка
К алгоритму не относится, но т.к реализовано на питоне
3) list это ключевое слово в языке, крайне не рекомендуется его переопределять.

Comments

[Moskaa]

Я думал, что должно возвращаться значение, а не индекс. О втором я знаю, благо это легко изменить.
Насчёт третьего я конечно знал, что list - это какое-то ключевое слово, но чтобы настолько, в будущем учту.

Спасибо за примечание!