Copyright by Dr. Marek A. Suchenek 2012,2013,2014
This material is intended for future publication.
Absolutely positively no copying no printing no sharing no distributing of ANY kind, please.

Example of computation of worst case (Binary Search)

Result  : worst-case running time

T(n) = ⌊(Subscript[lg, 2])n⌋+1.

Binary search, ordered.

Find an item x in an ordered array I based only of comparisons of x to elements of I.

size (I) - number of elements to be searched (= n).

I[0] ≤ I[1] ≤ I[2] ≤ ... ≤ I[i - 1] ≤ 
                        I[i] ≤ ... ≤ I[n - 1]
                                   ^ 
         midpoint  i =⌊ ((n-1)/2)⌋

Formulas we will use:

For every m∈ℤ,
m=⌊(m/2)⌋+⌈(m/2)⌉ (same as   m-⌊(m/2)⌋=⌈(m/2)⌉)

⌈(m/2)⌉=⌊((m+1)/2)⌋ (hence   m-⌊(m/2)⌋=⌊((m+1)/2)⌋)

Exercise: prove both (should be easy).

Note : ⌊(n/2)⌋ is performed by a binary operation"shift one position to the right".

Unsucessful search for x > I[n-1] yields an example of worst-case number of comparisons.

If I contains no duplicates then sucessful search for x = I[n-1] yields an example of worst-case number of comparisons as well.

Optional exercise for smart students
 Prove the above two statements.

We will prove that this worst-case number of comparisons is exactly equal to ⌊(Subscript[lg, 2])n⌋+1.

First, we will show, by induction on k, that the number of elements that still need to be serched (those are the elements after the last midpoint) after k comparisons is given by this formula
⌊(n/(2^k))⌋

Proof by induction on k.

Basis step, k = 1.
 The midpoint is ⌊ ((n-1)/2)⌋, and x>I[ ⌊ ((n-1)/2)⌋].
The number of elements of I after the midpoint is
(n-1)(*the greatest index*)-(⌊ ((n-1)/2)⌋+1)(*the least index*)+1=
=n-1-⌊ ((n-1)/2)⌋=⌈ ((n-1)/2)⌉=⌊ (n/2)⌋ = ⌊ (n/(2^1))⌋
This completes the basis step.

Side conclusion. While searching for an element larger than any element of the array of m elements, after one (and unsuccessful) trial,⌊ (m/2)⌋ elements (those after the midpoint) still need to be searched.  


Inductive step, k ≥ 1.

Inductive hypothesis. 

Assume that after k comparisons there are still ⌊ (n/(2^k))⌋ elements (after the last midpoint) to be searched.

Using the above side conclusion we infer that after next comparison the number of elements that still need to be searched is:
⌊ ((⌊ (n/(2^k))⌋)/2)⌋ =(* because ⌊(n/(2^k))⌋ is shifting n 
k  positions to the right and  
⌊(n/(2^(k+1)))⌋ is shifting n 
k+1  positions to the right *) ⌊ (n/(2^(k+1)))⌋ 

This completes the inductive step.
This completes the proof that the number of elements that still need to be serched (those are the elements after the last midpoint) after k comparisons is given by this formula
⌊(n/(2^k))⌋

Now, what is the smallest k that makes the number of elements (after the last midpoint) that still need to be searched equal to 0?

What is the smallest k that makes

⌊ (n/(2^k))⌋=0?

What is the smallest k that makes
0≤  (n/(2^k))<1?

What is the smallest k that makes
  n<(2^k) ?

What is the smallest k that makes
  n+1≤ (2^k) ?

What is the smallest  k that satisfies
  (Subscript[lg, 2])(n+1)≤(Subscript[lg, 2]) (2^k) ?

What is the smallest  k that satisfies
  (Subscript[lg, 2])(n+1)≤k ?

Answer :

⌈(Subscript[lg, 2])(n+1)⌉

same as :

⌊(Subscript[lg, 2])n⌋+1

Plot[{⌈Log2[n+1]⌉,Log2[n+1]},{n,1,127}]