第七章 顺序查找和折半查找

基础概念

相关提炼内容见 binary-search array-list。

顺序查找

• 一般线性表的顺序查找
• 有序表的顺序查找

折半查找 / 二分查找

二分查找：Leecode 算法题：二分查找，题解见 binary-search

分块查找 / 索引顺序查找

平均查找长度

内和索引表中均采用顺序查找时

$$ASL=L_I+L_S=\frac{s^2+2s+n}{2s}$$

当$s=\sqrt{n}$ 时，平均查找长度取最小值$\sqrt{n}+1$

若对索引表采用折半查找时，则平均查找长度为

$$ASL=L_I+L_S=\lceil {\log }_2(b+1)\rceil +\frac{s+1}{2}$$

参考资料

• Leecode 算法题：二分查找 todo