Ahmad Qassym Ответов: 3

Почему мы пишем m+1 в последней строке двоичного поискового кода ?

def bsearch2 ( lst : list , key , lo :int , hi : int ):
    if lo == hi :
       return None # key not in empty segment
    m = ( lo + hi )//2 # position of root
    if lst [ m] == key :
        return m
    elif lst [ m] > key :
        return bsearch2 ( lst , key , lo , m)
    else : # lst[m] < key
        return bsearch2 ( lst , key , m +1 , hi )


Что я уже пробовал:

.................................................................

3 Ответов

Рейтинг:
5

Patrice T

Тот же вопрос, что и Почему мы добавляем 1 к r + m в последней строке ?[^] в основном с тем же кодом.
m+1 не одинок, он соперничает с другими переменными:

elif lst [ m] > key :
    return bsearch2 ( lst , key , lo , m )
else : # lst[m] < key
    return bsearch2 ( lst , key , m +1 , hi )

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

Рейтинг:
20

OriginalGriff

Как вы думаете, почему? Что изменится, если ты этого не сделаешь?

Сделать две вещи:
1) прочтите это: Алгоритм бинарного поиска - Википедия[^]
И
2) разбейте отладчик и следуйте своему коду как есть. Теперь измените "М + 1" на "М" и повторите попытку. Что изменилось? Почему это не сработало?

Попробуйте - потратьте некоторое время на то, чтобы посмотреть, что происходит, и подумайте об этом. Это даст вам гораздо лучшее представление о том, как работают алгоритмы в целом, что просто говорят "потому что ..."

Ahmad Qassym

проблема в том, что у меня есть экзамен по программированию через несколько дней, и нет времени изучать новые вещи или методы :D

Рейтинг:
15

Richard MacCutchan

Тот же самый ответ, который вам дали четыре дня назад. https://www.codeproject.com/Questions/5279256/Why-do-we-add-1-to-the-r-plus-m-in-the-last-line[^]. Вы следовали предложениям?