Example 2: Binary Search
Using iterative approach, the following model can be set up for the average number of comparisons for binary search work.
Assume the total number of elements in an array, n = 2k – 1
Then,
Pr (comparisons = 1) = 
Pr (comparisons = 2) = 
.
.
Pr (comparisons = k) = 
Therefore, assuming element is in array
Average number of comparisons 
Solving the numerator, we have
 
Share with your friends: |
