Может кто-то простыми словами пояснить как работают эти строчки кода?

Question

[hlystik]

Вот полный код.

def binary_search(lst, search_item):
    low = 0
    high = len(lst) - 1
    search_res = False

    while low <= high and not search_res:
        middle = (low + high) // 2
        guess = lst[middle]

        if guess == search_item:
            search_res = True

        if guess > search_item:
            high = middle - 1

        else:
            low = middle + 1
    return search_res

lst = [1,3,6,5,70,6,6,7]
lst = sorted(lst)
print(lst)

value = 20
result = binary_search(lst, value)
if result:
    print("Элемент найден!")
    print(value)
else:
    print("Элемент не найден.")

Проще говоря, мне не понятно как работает конкретно эта часть кода.

if guess > search_item:
            high = middle - 1

        else:
            low = middle + 1

Приношу извинения за столь глупый вопрос, просто зашёл в тупик из которого не могу выйти уже как два дня.

Answer 1

[Владимир Куц]

1. Cортируем список
2. Берем элемент посредине списка
3. Сравниваем с искомым
4. Если искомое равно элементу - ура - нашли
5. Если искомое больше элемента, то слева от элемента искать смысла нет - там числа заведомо меньшие - берем часть списка справа от элемента - с позиции +1 и до конца
6. Если искомое меньше элемента, то справа от элемента искать смысла нет - там числа заведомо большие - берем часть списка слева от элемента - от начала и до позиции -1 до элемента
7. Повторяем процедуру с шага 2 с новой частью списка.

[1, 3, 5, 6, 6, 6, 7, 70] 
 0, 1, 2, 3, 4, 5, 6, 7   # позиции элементов
элемент посредине - это 6 на позиции 3.

Сравниваем с 20. 20 больше 6

Значит слева от 6-ки смотреть числа смысла нет - это числа [1, 3, 5].

Сама 6 тоже не нужна - мы ее уже сравнили с искомым и уже узнали что это не то число.

Значит берем часть списка справа - 
с позиции +1 - то есть с 4-й позиции и до конца - [6, 6, 7, 70]

и т.п.

Так понятно?

Comments

[Spooky 2020]

Здрасте. А вот это зачем: high = len(lst) - 1
В пайтоне len() будет вызываться каждую итерацию, если ее в условии цикла разместить? Оно не кэшируется?

[Владимир Куц]

Spooky 2020,
high = len(lst) - 1
Это позиция последнего элемента. Так как счет идет с 0 - то индекс будет на единицу меньше длины.

В пайтоне len() будет вызываться каждую итерацию, если ее в условии цикла разместить? Оно не кэшируется?

А зачем ее там размещать? len тут используется только для того чтобы получить исходную длину списка - и все... С чего ей кешироваться?

[Spooky 2020]

Владимир Куц, Я про то почему так не сделали while low < len(lst) and not search_res:
В этом случае len() каждую итерацию вызывается? Или ее результат кэшируется и в дальнейшем подставляется?

[Владимир Куц]

Spooky 2020, потому что длина lst у нас не меняется. Мы исходный массив lst не трогаем.
А границы в которых ищем в этом исходном массиве - мы сами задаем через low и high

[hlystik]

Владимир Куц, спасибо за помощь)