Python двоичного поиска (максимальное число итераций)

Question

Я прибегая к помощи двоичного поиска в питоне, и я нашел это: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html

Это говорит о том, что общее соотношение между макс. числа итераций (то же, что и Probe справа?) и N (размер списка) задается N = 2^k -1, где k - максимальное количество итераций.

Однако из моего понимания, если не вообще отношения быть N = 2^k
Поскольку каждый раз после поиска, мы разделили бы из списка на 2, пока мы не получим до 1.

Поэтому максимальное число итераций is log2 N вместо log2 (N+1)

У меня есть googled это, и я нашел, что один сайт поддерживает мой ответ, но без особого объяснения. (ссылка здесь: http://codingexplained.com/coding/theory/binary-search-algorithm)

Может ли кто-то объяснить математику позади нее? Благодарю.

Answer 1

Позвольте P(n) быть числом зондов, необходимых для n элементов. Тогда можно записать следующее уравнение:

P(0) = 0 
P(n) = 1 + P((n-1)/2) 

Объяснение: Сначала мы не имеем никаких элементов - ничего не делать. Затем мы делаем 1 зонд, и мы остаемся с (n-1)/2 элементами (мы бросаем 1 прочь, потому что мы только что проверили его), поэтому нам нужно сделать P((n-1)/2).

Результат для P(n) из этого уравнения будет floor(lg(n+1)). Вы можете проверить это на некоторых примерах (например, n = 6 и n = 7), или вы можете прочитать о том, как решать рекурсивные уравнения