Prove by mathematical induction For all k in 0 if binary sea

Prove by mathematical induction. For all k in {0,....}, if binary search is applied to an array of length n and has not terminated after k (unsuccessful) probes, then the length of the current sublist must less than or equal to n/2^k.

Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Above is a array of sorted natural numbers. Let\'s say we want to find the element 2 from the above list.
K is the number of unsuccessful probe.
We have to prove: For array of size n current Sub-list must less than or equal to n/2^k where k is number of unsuccessful probe

At the very beginning of the binary search
number of unsuccessful probe = 0
Sub-list size = 32 as there is no Sub-list done yet
n/2^k = 32/2^0 = 32
So, we can see here Sub-list size and n/2^k are both equal. So, for k=0 the statement is true.

So, for the first phase of binary search the entire list would be divided into 2 Sub-list
Sub-list 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Sub-list 2: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
number of unsuccessful probe = 1
Sub-list size = 16
n/2^k = 32/2^1 = 16
So, we can see here Sub-list size and n/2^k are both equal. So, for k=1 the statement is true.

For the second phase of binary search the Sub-list 1 from first phase would be divided into 2 Sub-list
Sub-list 1: 1 2 3 4 5 6 7 8
Sub-list 2: 9 10 11 12 13 14 15 16
number of unsuccessful probe = 2
Sub-list size = 8
n/2^k = 32/2^2 = 8
So, we can see here Sub-list size and n/2^k are both equal. So, for k=2 the statement is true.

For the third phase of binary search the Sub-list 1 from second phase would be divided into 2 Sub-list
Sub-list 1: 1 2 3 4
Sub-list 2: 5 6 7 8
number of unsuccessful probe = 3
Sub-list size = 4
n/2^k = 32/2^3 = 4
So, we can see here Sub-list size and n/2^k are both equal. So, for k=3 the statement is true.

For the forth phase of binary search the Sub-list 1 from third phase would be divided into 2 Sub-list
Sub-list 1: 1 2
Sub-list 2: 3 4
number of unsuccessful probe = 4
Sub-list size = 2
n/2^k = 32/2^4 = 2
So, we can see here Sub-list size and n/2^k are both equal. So, for k=4 the statement is true.

In fifth phase the element would be found hence binary search would be terminated.

So, we can see For all k in {0,1,2,3...} the statement is true.