Question

用折半查找在有序表（1,3,5,7,9,10,12,14,16,18,19） 中查找关键字3,需要比较的次数是？

Answer 1

构造折半查找的判定树就可以了
第1层1个结点
第2层2个结点
第3层4个结点
第4层8个结点，共计1+2 + 4 + 8 = 15
剩余30-15 = 15在第5层，也就是说比较次数为5次，因此答案正确

Answer 2

一共11个关键字，设第一个数1在数组R中的位置是R[0]，剩余的数依次存放，数19在R[10]。
第一趟，取中间位置为（0+10）/2＝5，数为10，比3大，此时看左半区间。
第二趟，取中间位置（0+4）/2＝2，数为5，比3大，看左半区间。
第三趟，取中间位置（0+1）/2＝0，数为1，比3小，看右半区间。
第四趟，查找成功。
所以需要比较4趟。