@Clazzzer123

Не понимаю часть алгоритма бинарного поиска?

Есть код

def binary_search(mylist, item):
    start = 0
    stop = len(my_list) - 1

    while start <= stop:
        mid = (start + stop) // 2
        guess = mylist[mid]
        if guess  == item:
            return mid
        if guess > item:
            stop = mid - 1
        else:
            start = mid + 1
    return None

my_list = [1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,19]
print(binary_search(my_list, 3))

Не могу понять зачем в строке
stop = len(my_list) - 1
делать "-1"? почему нельзя написать просто stop = len(my_list)?
  • Вопрос задан
  • 205 просмотров
Пригласить эксперта
Ответы на вопрос 2
fox_12
@fox_12 Куратор тега Python
Расставляю биты, управляю заряженными частицами
Наверное потому что в массиве индексы начинаются с 0. И потому индекс последнего элемента массива будет равне длине массива минус 1

почему нельзя написать просто stop = len(my_list)

потому что в таком случае есть вероятность вылететь с ошибкой при обращении к несуществующему элементу массива
Ответ написан
longclaps
@longclaps
Вот почему
def binary_search(mylist, item):
    start = 0
    stop = len(my_list) # верни -1

    while start <= stop:
        mid = (start + stop) // 2
        guess = mylist[mid]
        if guess  == item:
            return mid
        if guess > item:
            stop = mid - 1
        else:
            start = mid + 1
    return None

my_list = [1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,19]
print(binary_search(my_list, 20))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
от 1 300 до 2 500 usd.
ТК «Альфа» Тверь
До 55 000 руб.
Alytics Зеленоград
от 100 000 до 130 000 руб.
21 окт. 2019, в 22:35
500 руб./за проект
21 окт. 2019, в 21:56
10000 руб./за проект
21 окт. 2019, в 21:06
600 руб./в час