Analysis of Algorithms : An Active Learning Approach

52 SEARCHING AND SELECTION ALGORITHMS

2.2.3

1. Draw the decision tree for the binary search algorithm for a list of 12 ele-
   ments. For the internal nodes of your decision tree, the node should be
   labeled with the element checked, the left child should represent what hap-
   pens if the target is less than the element checked, and the right child should
   represent what happens if the target is greater than the element checked.


2. The analysis of binary search in this chapter assumed that the size was always
   2 k
   1 for some value of k. For this question, we will explore other possibil-
   ities for the size:
   a. What is the worst case when N≠ 2 k
   1?
   b. What is the average case when N≠ 2 k
   1, assuming that the key is in
   the list? Hint: Think about what this change in size means for the bottom
   of the search tree.
   c. What is the average case when N≠ 2 k
   1, if the key might not be in the
   list?Hint: Think about what this change in size means for the bottom of
   the search tree.


3. When the collection of data is large, there can still be a large number of
   comparisons needed to do a binary search. For example, a telephone direc-
   tory of a large city could easily take about 25 comparisons per search. To
   improve this, multiway searching uses a general tree, which is a tree data
   structure that can have more than two children. In multiway searching, we
   store a few keys in each tree node, and the children represent the subtrees
   containing (a) the entries smaller than all the keys, (b) the entries larger than
   the first key but smaller than the rest, (c) the entries larger than the first two
   keys but smaller than the rest, and so on. The following figure shows an
   example of a general tree that can be used for multiway searching. In the
   root of this tree we have the keys of 6 and 10, so if we are looking for a key
   less than 6, we would take the left branch. If we are looking for a key
   between 6 and 10, we would take the middle branch, and for a key larger
   than 10, we would take the right branch.

■2.2.3 EXERCISES

6/10

2/4 8 12/14/16

1 3 5 7 9 11 13 15 17