2.2 BINARY SEARCH 49Building a decision tree for the search process can also help with this analy-
sis. The nodes of the decision tree would have the element that is checked at
each pass. Those elements that would be checked if the target is less than the
current element would go into the left subtree and those checked when the
target is greater would go into the right subtree. If our list had just seven ele-
ments, the tree that would result is shown in Fig. 2.1. In general, we know that
this tree is relatively balanced because we always choose the middle of the var-
ious parts of the list. So, we can use formulas related to binary trees from Sec-
tion 1.3.2 to get the number of comparisons.
Because we chose N = 2k 1, the resulting decision tree will be complete.
There will be k levels in the resulting tree, where k = lg(N + 1). Because we
do one comparison on each level, the most we do is lg(N + 1) comparisons.■ 2.2.2 Average-Case Analysis
As with sequential search, we will consider two situations when doing an aver-
age-case analysis. In the first, the target will always be in the list, and in the sec-
ond, the target may not be in the list.
The first situation will have N possible locations for the target. We will con-
sider each of these to be equivalent and so will give each a probability of 1/N.
If we consider the binary tree that represents this search process, we will see
that one comparison is done to find the element that is in the root of the tree
on level 1. Two comparisons are done to find the elements that are in the nodes
on level 2, and three comparisons are done to find the elements that are in the
nodes on level 3. In general, i comparisons are done to find the elements that
are in the nodes on level i. Section 1.3.2 showed that for a binary tree there are
2 i^1 nodes on level i, and when N = 2k 1, there are k levels in the tree. Thislist[4]list[2] list[6]list[1] list[3] list[5] list[7]■FIGURE 2.1
Decision tree for a
search of a list of
seven elements