Python binary search (maximum number of iterations)

Question

I searched the binary search in python and found this: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html

He said the overall ratio between max. the number of iterations (same as Probe on the right?) and N (list size) is specified N = 2^k -1, where k is the maximum number of iterations.

However, based on my understanding, there should not be a general relationship. N = 2^k
Like every time after a search, we would divide the list by 2 until we get 1.

Therefore, the maximum number of iterations log2 Ninsteadlog2 (N+1)

I have googled this, and I found that one website supports my answer, but without much explanation. (link here: http://codingexplained.com/coding/theory/binary-search-algorithm )

Can someone explain the math behind this? Thanks.

Answer 1

Let be the P(n)number of probes needed for the elements n. Then we can write the following equation:

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

Explanation: At first, we have no elements - there is nothing to do. Then we make 1 probe and we stay with the elements (n-1)/2(we throw 1 away because we just checked it), so we need to do P((n-1)/2)more.

P(n) floor(lg(n+1)). (, n = 6 n = 7), ,