采用折半查找,当查找成功时,最少比较次数为 次,如在上例中查找关键字值为18的结点, 只需一次比较。最多经过log2n次比较之后,待 查找子表要么为空,要么只剩下一个结点,所 以要确定查找失败需要log2n次或lg2n+1次比 较。可以证明,折半查找的平均查找长度是: 从折半查找的平均查找长度ASL来看,当表的长 度n很大时,该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表,若经常要进 行插入、删除操作,则元素排列费时太多,因 此折半查找比较适合于一经建立就很少改动而 又需要经常査找的线性表,较少查找而又经常 需要改动的线性表可以采用链接存储,使 序查找。 下一顶返回本章首页 下一页 上一页 采用折半查找，当查找成功时，最少比较次数为 一次，如在上例中查找关键字值为18的结点， 只需一次比较。最多经过log2n次比较之后，待 查找子表要么为空，要么只剩下一个结点，所 以要确定查找失败需要log2n次或log2n+1次比 较。可以证明，折半查找的平均查找长度是： 从折半查找的平均查找长度ASL来看，当表的长 度n很大时，该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表，若经常要进 行插入、删除操作，则元素排列费时太多，因 此折半查找比较适合于一经建立就很少改动而 又需要经常查找的线性表，较少查找而又经常 需要改动的线性表可以采用链接存储，使用顺 序查找