|
|
|
折半查找的基本思想是：设查找表的元素存储在一维数组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。
|
|
|
|
折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
