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 the number of significant bits in the binary representation of n, that is, to ⌊(Subscript[lg, 2])n⌋+1.

We will show that while searching for an element larger than any element of the array  A  of  m elements, after one comparison,⌊ (m/2)⌋ elements (those after the midpoint) still need to be searched.  

Since the binary representation of ⌊ (m/2)⌋ has one less bit than m has, this will show that in order to reduce the size of the set of elements still under search to 0,the number of comparisons must be equal to the number of significant bits in the binary representation of n.

Example. If n = 10 ,or 1010 in binary, 

after first comparison (x>I[4]) there are still  5, or 101 in binary , elements to search, 

after second comparison  (x>I[7])there are still  2, or 10 in binary , elements to search,

after third comparison  (x>I[8])there is still  1, also 1 in binary , element to search,and 

after fourth comparison  (x>I[9])there are   no elements to search. 

Thus the search was completed in 4 comparisons, and that is also the number of significabt bits in the binary representation of 10. 


 The midpoint is ⌊ ((m-1)/2)⌋, and x>A[ ⌊ ((m-1)/2)⌋].
The number of elements of A after the midpoint is
(m-1)(*the greatest index*)-(⌊ ((m-1)/2)⌋+1)(*the least index*)+1=
=m-1-⌊ ((m-1)/2)⌋=⌈ ((m-1)/2)⌉=⌊ (m/2)⌋

So, what is the number of significant bits in the binary representation of n?

Answer :

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

Plot[{⌊Log2[n]⌋+1,Log2[n+1]},{n,1,127}]