二分查找法平均查找长度公式

Question

如题所述

Answer 1

这个公式是ASL = (log2(n+1) - 1) * (n+1) / n。
n值较大时，(n+1)/n可以忽略。二分查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列，所以它适用于表不易变动而且经常进行查找的情况。
二分查找也称为折半查找，其基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置的关键字等于给定值或者查找区间没有元素时（表名查找不成功）为止。