查找

顺序查找

　　无序线性表的顺序查找

　　有序的顺序表的顺序查找

　　查找可以提前结束。（A[i] < key ，key > A[i]）

　　查找判定树：若有n个查找成功结点，则必有相应的 n+1 个查找事变结点。

折半查找

　　需要有序（缩小范围），并且是顺序存储结构（需要定位查找区域）

　　时间复杂度  O(log₂n)

分块查找

　　又叫索引顺序查找，有顺序查找和折半查找的优点。

　　分块，块间有序，块内无序。索引表内的每个元素含有块的最大关键字和各块中第一个元素的地址。

　　查找=  索引查找+ 块内查找。

　　长度为 n 的查找表均匀的分为 b 块，每块有 s 个记录。 s = n ^1/2 ，平均查找长度最小。