Binary Search
Binary search finds the key by comparing the key with themiddle element of a sorted array and choosing to continue the search to loweror upper part of the array. The iterative algorithm is faster than therecursive algorithm, which requires index to the section of array to search.
Algorithm BinarySearch(A[0...n-1], K)
l ← 0; r ← n-1 // section of the array to search
while l ≤ r do
m ← floor((l+r)/2)
if K = A[m] thenreturn m
else if K < A[m]then r ← m-1
else l ← m+1
return -1 // key not found
Note the pseudo code uses two way cost, meaning = and <are determined separately. We'll calculate the cost assuming 3-way comparison,meaning = and < are compared together in a single calculation. The 3-way comparisonwill be are unit operation.
The worst case is when the key is not found or found when l = r.Then the number of comparisons are
Cworst(n) = Cworst(floor(n/2)) + 1
IC Cworst(1) = 1
The floor function because themiddle value is not included in the next range of the array to search. Also,the initial case is cost because the key is checked.
Master theorem can be used to determine the order of growthbut the exact value is (using smoothing rule)
Cworst(n) = lg n + 1
The general solution is
Cworst(n) = floor(lg n) + 1 =ceiling(lg(n+ 1))
Also the average case
Cavg(n) ≈ lg n
makes only a few less calls.
Can binary search be applied to link list? is it efficient?
What implication does this have on look-up tables?
The author mentions that this algorithm is not really adivide and conquer algorithm. Really it is decrease and divide.
Binary Tree Searches
Binary trees have left and right trees, TL and TR
Algorithm Height(T)
if T is empty then return-1
else return max(Height(TL), Height(TR)) +1
The number of additions are
A(size(T)) = A(size(TL)) + A(size(TR)) +1
IC A(0) = 0
We can solve to get A(n) = n
But addition is not the most frequent operation. Thecomparison in the if statement (checking for T empty)is the most common. This is done on all calls.
There is trick to determine the number of comparisons.
Introduce the concept of internal and external nodes.
Add empty external nodes to the tree.
Note that the supplemented tree (addition of external nodes)is proper binary
n = number ofinternal nodes, size of the tree
x = number ofexternal nodes
The number of children in a proper binary tree is 2n. Why? becauseevery internal has two children and the externals have none.
But all the nodes of the trees are children except the root.It has no parent.
2n = x + n - 1
x= n + 1
The number of comparisons for null tree is x + n,while the number addition is the number of internal.
The empty external represent the empty tree in the recursivecall.
C(n) = x + n = 2n+ 1
More than trice the number of comparisons.
Binary Tree traversal
Three kinds: preorder, post-order and in-order
What are the costs?
What are the cost for searching fora key?
