Question

如何理解二分查找？

Answer 1

设关键字个数为n,在各关键字等概率查找的前提下

1、顺序查找的平均查找长度ASL=(n+1)/2

2、在n趋于无穷大时，折半查找的ASL=((n+1)log2(n+1))/n - 1，当n大于50时，ASL约等于log2(n+1)-1

3、设分块查找中将长为 n 的表分成均等的b个块,每块s个元素，则b= (n / s)上取整，如果索引表中采用顺序查找，则ASL=(b+1)/2+(s+1)/2；如果索引表中采用折半查找，则ASL=(s+1)/2+log2(b+1)-1。

扩展资料：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

参考资料来源：百度百科-二分查找