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

Question

[Дима Щеглов]

Не могу понять почему не работает алгоритм:

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()

Comments

[Ivan Yakushenko]

эх, вот если бы ты указал как этот "алгоритм" должен работать... а если бы еще и пример вводных данных дал

[Дима Щеглов]

Ivan Yakushenko, ахахахах, да внатуре сложный для понимания алгоритм в котором ничего не понятно :(((((

[Ivan Yakushenko]

Дима Щеглов, вопрос не в сложности, а в отношении. Тебе необходима помощь, но ты даже не предоставляешь вводные данные и ожидаемый результат. Тут не у всех есть желание построчно разбирать код, пускай в нём хоть 10 строчек.

[Дима Щеглов]

Ivan Yakushenko, ахахахахахх сынок... "но ты же не предоставляешь вводные данные :(((",

x = []
for i in range(1,101):
x.append(i)
binary_search(x,12)

Блиииин ожидаемый результат оказывается 12 :((((((.
Ты говоришь об отношении, но ничего толкового не пишешь.Зачем тогда ты пишешь что-либо к вопросу, если априори ты ничего не проверял?

[Ivan Yakushenko]

Дима Щеглов, я написал комментарий, а не ответ.

Тут не у всех есть желание построчно разбирать код, пускай в нём хоть 10 строчек.

Было бы неплохо, если бы ты прочитал то, что я написал, прежде чем что ли мне предъявлять.
И давай без фамильярности.

[Дима Щеглов]

Ivan Yakushenko, На счет фамильярности, не ты ли оставлял комментарий (который впоследствии удалил :) ) о том что я "глупый".
Я в очередной раз убедился, что ты дальше двух строк не читаешь. Скажи как тебе выдали статус "Куратор тега"?

[Ivan Yakushenko]

Дима Щеглов,

На счет фамильярности, не ты ли оставлял комментарий (который впоследствии удалил :) ) о том что я "глупый".

Да, я. И я за это извиняюсь, написал не подумав в плохом настроении.

Я в очередной раз убедился, что ты дальше двух строк не читаешь

Я прекрасно читаю всё, что мне пишут. С восприятием так же проблем не наблюдается.

Скажи как тебе выдали статус "Куратор тега"?

Доступ к кураторству выдается за активность. Никакого "тестирования" и "отбора" нет, если ты об этом.

Answer 1

[Antonio Solo]

1) для начала отступ 4 пробела как написано в pep8
2) во вторых написать что именно вы ожидаете от вашего алгоритма, и что на ваш взгляд он делает не так

Comments

[Дима Щеглов]

Не знаю, в чем проблема прочитать название функции, pep8 не обязательно для синтаксиса

[Roman K]

Дима Щеглов, не знаю в чём проблема прочитать код стандартной библиотеки bisect

[Дима Щеглов]

Roman Kitaev, тип, если для тебя проблема написать простой алгоритм и вместо этого ты подрубаешь библиотеку, то у меня для тебя плохие новости...

[Roman K]

Дима Щеглов, ты ещё так юн:)

Answer 2

[Wataru]

Определитесь со смыслом start и finish. start - это первый элемент интервала, в котором искомый x может быть. finish, судя по тому, что он равен сначала len(lst) - это за концом интервала (не входит в него).

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

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

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

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

Comments

[Дима Щеглов]

Бесспорно ваш вариант является отличным решение данного алгоритма, но я понял как его решить. Достаточно было поставить <= вместо знака <.

[Wataru]

Дима Щеглов, Я об этом и написал в самом конце моего ответа. Но надо еще присвоение в начале исправить. Иначе алгоритм может упасть с выходом за границу массива.