Binary search finds the key by comparing the key with the middle element of a sorted array and choosing to continue the search to lower or upper part of the array. The iterative algorithm is faster than the recursive 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] then return 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 comparison will 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 the middle 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 growth but 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 a divide and conquer algorithm. Really it is decrease and divide.
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. The comparison 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 of internal nodes, size of the tree
x = number of external nodes
The number of children in a proper binary tree is 2n. Why? because every 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 recursive call.
C(n) = x + n = 2n + 1
More than trice the number of comparisons.
Three kinds: preorder, post-order and in-order
What are the costs?
What are the cost for searching for a key?