[已解决]折半查找

songsinuo

请帮忙解释一下为什么是4次三次

请帮忙解释一下

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-10-17 13:05:39

折半查找法步骤：
① 首先确定整个查找区间的中间位置 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

跳转到最佳答案楼层

傻眼貓咪

折半查找法步骤：
① 首先确定整个查找区间的中间位置 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

非常感谢，还有个疑问：对半查找 不是向下取整吗？为啥每次都取两个值做比较呀

傻眼貓咪

songsinuo 发表于 2021-10-17 22:34
非常感谢，还有个疑问：对半查找 不是向下取整吗？为啥每次都取两个值做比较呀

没错，只是这样比较清楚知道中间值是什么，做比较时候向下取整