Question

假定对有序标，（3,7,24,42,54,63,72,87,95）进行折半查找，试回答下列问题

（1）画出描述折半查找过程的判定树；
（2）若查找元素42，需一次与那些元素比较？

Answer 1

下标 1   2   3   4   5   6   7   8   9
元素 3   7   24  42  54  63  72  87  95

low=下标1, high=下标9, mid=(low+high)/2=(1+9)/2=5(下标)
下标5的元素是[5]=54,这是判定树的根结点.
整个计算过程如下:

(1+9)/2=5 -> [5]=54  (这是判定树的根结点)

(1+4)/2=2 -> [2]=7   (根结点的左分支结点)

(1+1)/2=1 -> [1]=3

(3+4)/2=3 -> [3]=24

(4+4)/2=4 -> [4]=42

(6+9)/2=7 -> [7]=72  (根结点的右分支结点)

(6+6)/2=6 -> [6]=63

(8+9)/2=8 -> [8]=87

(9+9)/2=9 -> [9]=95

画出描述折半查找过程的判定树:

             54
         /       \
        7        72
       / \      /  \
      3   24   63  87
           \         \
            42       95


根据上图可知,
若查找元素42,需要依次与这几个元素进行比较: 54, 7, 24, 42