|
折半查找的基本思想是:设查找表的元素存储在一维数组r[1…n]中,那么在表中的元素已经按关键字递增(或递减)的方式排序的情况下,可进行折半查找。其方法是:首先将待查的key值与表r中间位置上(下标为mid)记录的关键字进行比较,若相等则查找成功;若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1…n]中,下一步应在后半个子表中再进行折半查找;若key<r[mid].key,说明待查记录只可能在前半个子表r[1…mid-1]中,下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围,直到查找成功或子表为空时失败为止。
|
|
|
折半查找的性能分析:折半查找的过程可以用一棵二叉树描述,不妨设节点总数为n=2h-1,则判定树是深度为h=log2(n+1)的满二叉树。在等概率情况下,折半查找的平均查找长度为。
|
|
|
当n值较大时,ASLbs≈log2(n+1)-1。
|
|
|
折半查找比顺序查找的效率高,但它要求查找表进行顺序存储并且按关键字有序排列,因此对表进行元素的插入和删除时,需要移动大量的元素,所以折半查找适用于表不易变动,且又经常进行查找的情况。
|
|
|