ayluP_amaK
@ayluP_amaK
Senior Python developer

Как исправить данный алгоритм?

Не могу понять почему не работает алгоритм:
def binary_search(lst,x):
	start = 0
	finish = len(lst)
	while start < finish:
		mid = (start + finish)//2
		guess = lst[mid]
		if guess == x:
			return mid
		if guess > x:
			finish = mid - 1
		else:
			start = mid + 1

x = []
for i in range(1,101):
	x.append(i)
binary_search(x,12)
input()
  • Вопрос задан
  • 163 просмотра
Пригласить эксперта
Ответы на вопрос 3
@bacon
А чё сразу сложный? и "Senior Python developer" не умеет дебажить? Ну так printы хотя бы расставь, чтобы видеть шаги выполнения, а лучше освой pdb.
Ответ написан
solotony
@solotony
ушел пить чай %)
1) для начала отступ 4 пробела как написано в pep8
2) во вторых написать что именно вы ожидаете от вашего алгоритма, и что на ваш взгляд он делает не так
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Определитесь со смыслом start и finish. start - это первый элемент интервала, в котором искомый x может быть. finish, судя по тому, что он равен сначала len(lst) - это за концом интервала (не входит в него).

Значит, исходя из этого, надо цикл гнать пока start < finish - тут правильно.

При переходе наверх надо start делать mid+1 - тут правильно.

При переходе вниз надо finish делать mid - тут ошибка! Ведь только что рассмотренный элемент вы выбрасываете, раз он не подошел. Но предыдущий за ним может быть искомым. Нельзя делать finish = mid-1 - вы теряете потенциально важный элемент.

Другой вариант исправления - изменить смысл finish быть концом отрезка включительно. Тогда присвоения в цикле правильные, но неверно условие цикла и инициализация. Нужно гнать цекл пока start <= finish и изначально присваивать len(lst)-1.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы