折半查找
请帮忙解释一下为什么是4次三次折半查找法步骤：
① 首先确定整个查找区间的中间位置 mid = (left + right)/2 。
② 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后（右）半个区域继续进行折半查找；若小于，则在前（左）半个区域继续进行折半查找。
③ 对确定的缩小区域再按折半公式，重复上述步骤。
如上：先查找 15
列表 {7, 15, 18, 21, 27, 36, 42, 48, 51, 54, 60, 72} 共12个元素，对半是 36, 42
第 1 次比较：待查关键值是 15（与 36 比较，不相等，36 大于 15，往右查找）。重复折半列表 {7, 15, 18, 21, 27}，对半是 18, 21
第 2 次比较：待查关键值是 15（与 18 比较，不相等，18 大于 15，往右查找）。重复折半列表 {7, 15}，对半是 7, 15
第 3 次比较：待查关键值是 15（与 7 比较，不相等，7 小于 15，往左查找）。
第 4 次比较：待查关键值是 15（与 15 比较，相等）。共 4 次比较
查找 38
列表 {7, 15, 18, 21, 27, 36, 42, 48, 51, 54, 60, 72} 共12个元素，对半是 36, 42
第 1 次比较：待查关键值是 38（与 36 比较，不相等，36 小于 38，往左查找）。重复折半列表 {42, 48, 51, 54, 60, 72}，对半是 51, 54
第 2 次比较：待查关键值是 38（与 51 比较，不相等，51 大于 38，往右查找）。重复折半列表 {42, 48}，对半是 42, 48
第 3 次比较：待查关键值是 38（与 42 比较，不相等，42 大于 38，往右查找，但是数组往右已经没有值了，所以答案是 38 没有在 列表里）。共 3 次比较
答案：4 和 3
非常感谢，还有个疑问：对半查找 不是向下取整吗？为啥每次都取两个值做比较呀 songsinuo 发表于 2021-10-17 22:34
非常感谢，还有个疑问：对半查找 不是向下取整吗？为啥每次都取两个值做比较呀
没错，只是这样比较清楚知道中间值是什么，做比较时候向下取整
页:
[1]