问题 填空题

在顺序表(6, 10, 16, 18, 25, 28, 30, 48, 50, 52) 中,用二分查找法查找关键码值20,则需要进行关键码比较次数为______。

答案

参考答案:4次

解析:
二分法查找方法:首先用要查找的关键码值与中间位置节点的关键码值比较。若比较相等则查找完成,不等则根据比较结构确定下一步的查找应在哪一个子表进行,如此下去,直到找到满足条件的节点,或者确定表中无这样的节点。要求:要进行二分查找,则线性表节点必须按关键码值排好序,且线性表以顺序方式存储。二分查找的平均检索长度小,每经过一次关键码比较,则将查找范围缩小一半,因此经过log2n次比较可完成查找过程。本题中,顺序表有11个节点,且又查找失败,故需要比较4次。

选择题
问答题