跳到主要内容

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

[!info] 基础概念 相关提炼内容见 binary-search array-list。

顺序查找​

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

折半查找 / 二分查找​

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

分块查找 / 索引顺序查找​

平均查找长度​

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

ASL=LI+LS=s2+2s+n2sASL = L_I+L_S=\frac {s^2+2s+n}{2s}

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

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

ASL=LI+LS=⌈log⁡2(b+1)⌉+s+12ASL = L_I+L_S=\lceil\log_2(b+1)\rceil+\frac {s+1}2

参考资料​