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

>>>A warm-up optional exercise left to the students as individual reading.

Example of approximate computation of average case (Binary Search)
Carries on the details of computations in the textbook, Section 1.6.3  Average-Behavior Analysis, p. 57-59.

Results:

(Subscript[T, avg])(n) ≈Log2[n+1] - q ≈ Log2[n] - q

where q is the probability of sucessful search.

More precisely,

(Subscript[T, avg])(n)=Log2[n] - q + o(1) 

Also, for sufficiently large n (e.g., n ≥  1000)and any 0≤ q≤ 1:

Log2[n]-q ≤ (Subscript[T, avg])(n) < Log2[n]+.1-q

The following two results will also be tested by a program posted on class website

For every n,
Log2[n+1] ≤ (Subscript[T, avg]^fail)(n) < Log2[n+1]+.1

For every n > 394,
Log2[n+1]-1 ≤ (Subscript[T, avg]^succ)(n) < Log2[n+1]-.9



Binary search, ordered.

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

I[0] ≤ I[1] ≤ I[2] ≤ ... ≤ I[i - 1] ≤I[i] ≤ ... ≤ I[n - 1]
                                   
   size (I) - number of elements to be searched (= n).


Assume size(I) = n= (2^k) - 1 
(for simplicity only; the general case without the above assumption is analyzed at the end of this file, with exact computations contained in files AverageCaseOptimalityBinSearch.nb and AverageCaseOptimalityBinSearch.pdf posted on the class website)
   

I[0] ≤ I[1] ≤ I[2] ≤ ... ≤ I[i - 1] ≤
                        I[i] ≤ ... ≤ I[n - 1]
                                   ^ 
         midpoint  i =⌊ ((n-1)/2)⌋
(Exercise: Prove it!)

n= (2^k) - 1

n + 1= (2^k)

k = Log2[n+1];

We know already that k is the possibly largest number of comparisons made by binary search, both in successful and unsuccessful case.

T (n) - 
 number of comparisons performed while searching of an entry in an n - 
 element array I.
  
 
   Average - case running time for successful search

Let (Subscript[s, t]) be the number of elements of I that are found after exactly t comparisons by the binary search.

(Subscript[s, t])=(2^(t-1))

(Exercise. Prove it by induction on t!)
Let comp(i) be the number of comparisons needed to find I[i].

(Subscript[T, avg]^succ)(n) = (∑_(i=0)^(n-1))comp(i)×Pr(i)=(∑_(i=0)^(n-1))comp(i)×(1/n)=(1/n)(∑_(i=0)^(n-1))comp(i)=(1/n)(∑_(t=1)^k)t×(Subscript[s, t]) = [because (Subscript[s, t]) = (2^(t-1)); note that t ≥ 1 for one cannot find anything in 0 comparisons]=

(1/n)(∑_(t=1)^k)t×(2^(t-1))

(((n+1) Log2[n+1])/n)-1

Factor[(((n+1) Log2[n+1])/n)-1]

So, they are equal.

(((n+1) Log2[n+1])/n)-1=
=((n Log2[n+1])/n)-1+((Log2[n+1])/n)≈
[since ((Log2[n+1])/n)≈0 for large n]

≈Log2[n+1]-1.

More precisely,

(Subscript[T, avg]^succ)(n)=Log2[n+1]-1+o(1)=
=Log2[n]-1+o(1).

[For large n,Log2[n+1]≈Log2[n], for instance,for n>1000, Log2[n+1]<Log2[n×(1.001)] =
Log2[n]+Log2[1.001] = Log2[n]+0.0014419741739062604`]

For unsuccessful search, 

(Subscript[T, avg]^fail)(n) = Log2[n+1]=
= Log2[n]+o(1).

Hence, (Subscript[T, avg])(n)=q×(Subscript[T, avg]^succ)(n)+(1-q)×(Subscript[T, avg]^fail)(n) =

q×((((n+1) Log2[n+1])/n)-1)+ (1-q)×Log2[n+1]

Expand[%]

Log2[n+1]-q+((q Log2[n+1])/(n ))

So,

(Subscript[T, avg])(n)≈Log2[n+1]-q .

More precisely,

(Subscript[T, avg])(n)=Log2[n+1]-q +o(1)
=Log2[n]-q +o(1).

[For large n,Log2[n+1]≈Log2[n], for instance,for n>1000, Log2[n+1]<Log2[n×(1.001)] =
Log2[n]+Log2[1.001] = Log2[n]+0.0014419741739062604`]

End of the warm-up exercise <<<

Theorem 1.

Binary Search is average-case optimal in the class C of search algorithms  search an ordered array by comparisons of keys.


Input: array E of n elements;
		key x.

Output: and index i s.t. 
x = E[i] 
if found (successful search);
otherwise (unsuccessful search)
a pair of idicies -∞:0 if x < E[0]
or
a pair of idices i:i+1 if E[i]<x < E[i+1]
or
a pair of idices n-1:∞ if x > E[n-1]

Note: We do not need assumption n = (2^k)-1 here.

Asserted even probability distribution:

All successful search outcomes are equally likely
and
all unsuccessful search outcomes are equally likely.

(A case of uneven probability distribution will be tackled in Chapter 10 Section 4.)

The result is proven for any algorithm that searches via decision tree; in particular, for any algorithm that searches by comparisons of keys.

The computations below require the concept external path length and internal path length in a binary tree.

Here is an example of a decision tree for Binry Search.

TreePlot[{5->2,5->8,2->1,2->4,8->7,8->10,0->"-∞:0",1->0,3->"2:3",4-> 3,6->"5:6",7->6,10->9,10->"10:∞",0-> "0:1",1-> "1:2",3-> "3:4",4-> "4:5",6-> "6:7",7-> "7:8",9-> "8:9",9-> "9:10"},VertexLabeling->True,DirectedEdges->True,VertexRenderingFunction->({White,EdgeForm[Black],Disk[#,.3],Black,Text[#2,#1]}&),AspectRatio->0.55]

External nodes are green.  These are non-decision nodes that represent the final outcomes of unsuccessful searches.
All others are decision nodes or the final outcomes of successful searches.

The average number of comparisons performed by Binary Search with a decision tree T on n nodes is

(Subscript[T, avg])(n)=q×(Subscript[T, avg]^succ)(n)+(1-q)×(Subscript[T, avg]^fail)(n)=q×(((ipl(T))/n)+1)+(1-q)×((ipl(T)+2n)/(n+1))

(in file:http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageCaseSearchLowerBound.nb).

Therefore,all we have to demonstrate that the decision tree of Binary Search has the minimum internal path length.

All levels of every decision tree for Binary Search has all levels that are full except, perhaps, for the last level.

Therefore, the internal path length for each decision tree on n nodes for Binary Search is equal to:

(∑_(i=1)^n)⌊Log2[i]⌋.

Thus, the said decision tree has the minimum external path length.

End of proof.

Theorem 2.

The average number of comparisons of keys that Binary Search performs on the average while searching an n-element ordered array is equal to:

(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q ≈

≈Log2[n+1]+ϵ[n+1] -q,

where

β[x_]:=1+x-(2^x)

θ[x_]:=⌈x⌉-x

ϵ[x_]:=β[θ[Log2[x]]]

Proof. Let T be a deccision tree on n nodes for Binary Search.
As we shown in the proof of Theorem 1,
(Subscript[T, avg])(n)=q×(((ipl(T))/n)+1)+(1-q)×((ipl(T)+2n)/(n+1)).

Since T has ther minimum internal path length, we conclude

(Subscript[T, avg])(n)=q×((1/n)(Subscript[ipl, min])(n)+1)+(1-q)×(((Subscript[ipl, min])(n)+2n)/(n+1)).

Applying computations from file file:http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageCaseSearchLowerBound.nb, we conclude that 
(Subscript[T, avg])(n)=(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q ≈

≈Log2[n+1]+ϵ[n+1] -q

End of proof.

Note.
Function ϵ oscillates between 0 and  
1−lg e+lg lg e ≈0.08607133205593432

Plot[{ϵ[n],0.08607133205593431`,1},{n,0.9`,2.2`},PlotTheme->"Classic",PlotStyle-> {Thickness[Small]},AspectRatio->0.6`,Ticks->{{1,1.3862943611198906`,2,22,64,177,355,512,710,1024},{0,0.08607133205593431`,1}}]