Вот код, который я использовал для изучения вашей программы. pdb позволяет вам выполнить код по одной команде за один раз, используя s или перейти на следующую страницу pdb.set_trace(), используя c. Вы можете использовать его как это:
import pdb
def binary_search(a_list, item):
if not a_list:
return False
mid = len(a_list)//2
print "Middle is: {}".format(a_list[mid])
print a_list
print a_list, item
pdb.set_trace()
while len(a_list) > 0:
if a_list[mid] == item:
return mid
elif a_list[mid] > item:
return binary_search(a_list[:mid], item)
elif a_list[mid] < item:
return binary_search(a_list[mid:], item) + mid
else:
return False
Теперь, существует целый ряд проблем, связанных с вашей программой, в первую очередь сочетание циклов и рекурсии. Это редко бывает правильным. Я также укажу, что каждый случай в вашем цикле while имеет оператор return, поэтому цикл while имеет эффект, вызывающий поиск с размером списка 0, чтобы ничего не вернуть. Я сомневаюсь, что это то, что вы хотите.
Вторая проблема заключается в том, что вы пытаетесь вернуть либо индекс mid, либо False. Нет проблем с тем, что вы пытаетесь сделать. Проблема заключается в добавлении binary_search(...) к mid. Причина, по которой это плохо, заключается в том, что в Python False оценивает 0, когда вы используете его как число. Попробуйте запустить их в качестве переводчика:
False * 5 # => 0
False + 5 # => 5
False == 0 # => True
False is 0 # => False
Это означает, что если ваш код работал иначе и была неудачная поиск, вы все равно в конечном итоге возвращаются целое ответить много времени. Значение False будет потеряно в дополнение к mid. Чтобы этого избежать, код, приведенный ниже, не использует рекурсию, поэтому return False является окончательным. Он идет непосредственно на того, кто звонил binary_search в первую очередь, а не на какие-либо предыдущие рекурсивные вызовы.Можно еще написать рекурсивное решение, но вы почти наверняка должны иметь сравнение как if binary_search(...) is False: где-то в коде тем вам нужно будет беспокоиться о разнице между is и ==тогда вы можете захотеть использовать более is часто, что плохой идеей.
Я также считаю, что есть некоторые проблемы с a_list[mid:]. Я не подтвердил это, но я думаю, вы бы хотели, чтобы a_list[mid+1:], чтобы исключить средний элемент, который вы подтвердили, не является тем элементом, который вы ищете. В любом случае, альтернативный код, который у меня есть, не использует нарезку вообще, поэтому я не буду беспокоиться об этом.
Вот код, который, как я считаю, делает то, что вы хотите.
def binary_search(a_list, item):
if not a_list:
return False
mid = len(a_list)//2
start = 0 # new and important
end = len(a_list) # new and important
while start < end: # new and important
if a_list[mid] > item:
end = mid
mid = (end - start) // 2 # new and important
elif a_list[mid] < item:
start = mid + 1
mid = start + (end - start) // 2 # new and important
else:
return mid
return False
Примечание удаление рекурсивных вызовов и добавление start и end. Они отслеживают, какую часть списка, который вы ищете, вместо разделов списка, которые вы использовали раньше.
если эта функция возвращает индекс, если найден, или возвращает значение true, если найдено else false –