Бинарный поиск в Python не работает должным образом, отображаются только некоторые элементы в списке - PullRequest
Новая
       9

Бинарный поиск в Python не работает должным образом, отображаются только некоторые элементы в списке

0 голосов
/ 31 октября 2019

Мой код не работает должным образом и отображает только правильные результаты 3 элементов, а не тот, что во 2-м индексе. Я не написал бы, но я пошел от псевдокода, указанного на странице кусков GCSE для CS, который не работает, когда я конвертирую в Python. https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/3

my_list=['arnold', 'matt', 'david', 'james']

found = False
search_item = input("type a name to find")
start_range = 0
end_range = len(my_list)



while found == False and start_range <= end_range:
    mid = (start_range + end_range) //2

    if search_item == my_list[mid]:
        found == True
        print("item found")
    else:

        if my_list[mid] >= search_item:
            end_range = mid -1
        else:
            start_range = mid +1


if found == False:
    print("item not found")

Когда я запускаю приведенный выше код и набираю 'arnold', я получаю сообщение 'item found', которое печатается бесконечно, что пока нормально. Однако, если я набираю второй элемент из списка, в этом случае 'matt', я получаю сообщение 'item not found'

Если я набираю 'david' или 'james', это работает какну, так это только пункт во 2-м указателе.

Первоначально я преобразовал псевдокод GCSE bitesize в python, но он даже не работал. Я действительно запутался, у меня нет четкого представления о том, почему он не работает, но я чувствую, что он как-то связан с индексом или даже с переменной среднего.

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

1 Ответ

0 голосов
/ 31 октября 2019

У вас есть несколько вопросов, которые необходимо решить. Прежде всего, бинарный поиск требует сортировки списка, чтобы сравнения (т.е. my_list[mid] >= search_item) имели смысл. Далее вам нужно изменить found == True на found = True. То, как вы это делаете, это просто сравнение, а не установка значения на True.

Это должно выглядеть так: 

my_list=['arnold', 'matt', 'david', 'james']

found = False
search_item = input("type a name to find")
start_range = 0
end_range = len(my_list) - 1

# ADD THIS
my_list.sort()

while found == False and start_range <= end_range:
    mid = (start_range + end_range) //2

    if search_item == my_list[mid]:
        # CHANGE THIS
        found = True
        print("item found")
    else:

        if my_list[mid] >= search_item:
            end_range = mid -1
        else:
            start_range = mid +1

if found == False:
    print("item not found")
...