Это правильная реализация бинарного поиска?

Question

[slmuim]

Всем привет! Начал учить алгоритмы, попробовал написать бинарный поиск на Python но не пойму работает ли она верно. По времени работает так же как и обычный поиск.

def binary_search(n, lst):
    guess = 0
    while guess != n:
        mid = int(len(lst)/2)
        if lst[mid] == n:
            guess = lst[mid]
            return guess
        elif lst[mid] < n:
            lst = lst[mid:]
        else:
            lst = lst[:mid]

Answer 1

[Wataru]

Работает медленно, потому что вы обрезаете входной массив каждый раз. Для этого приходится обходить и копировать всю нужную часть. Поэтому суммарное время работы будет O(n).

Чтобы работало быстро вам надо не менять lst, а помнить индексы границ текущего куска.

Ещё, вам надо останавливаться, когда рассматриваемый кусок станет пустым, чтобы решение не вылетало, если искомого числа в списке нет.

И последнее, в питоне есть операция целочисленного деления - //. Используйте ее вместо приведения к int после деления.

Comments

[Alexandroppolus]

lst = lst[mid:] - это и есть обрезка массива? т.е. создается копия половины?

[Wataru]

Alexandroppolus, Ага.

Answer 2

[Vindicar]

Твоя реализация зациклится, если такого элемента нет в списке.

Answer 3

[GavriKos]

Не вдаваясь в логику поиска:
- а что будет если в lst не будет нужного элемента?
- что вообще возвращает метод?

UPD:
- а если мне надо найти 0 в массиве? ;-)