Question

救救吧~已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中

已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

34 56 58 63 94元素值

求 比较次数

Answer 1

2 1 3 4 4
对半查找是把已知元素与范围内元素的中间那个元素比较，大于中间元素就把范围锁定在中间元素后面开始的元素，小于就把元素范围锁定中间元素前面的元素
例如查找34：先是在下标0到下标11这12个元素15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 中查找，他们的中间元素是下标(0+11)/2，也就是下标5这个元素56，因为34<56，所以范围改为下标0到下标4这5个元素15, 26, 34, 39, 45，接着再与下标(0+4)/2=2这个元素34比较，此时已经找到了，因此查找34只要找2次即可，下面4个同理