第二章 查找

查找算法分为静态查找表与动态，其中，静态只能进行查找操作、动态可以在其中进行增删操作。

基于线性表的查找

顺序查找

[1,2,3,4,5,6,7,8,9]
当腰查找8时，查看下标为0的是否等于，不等于查看下标为1，依此类推。
若超出查找范围仍未找到，可以设定返回一个值。

二分查找

顺序查找的改进。
[1,2,3,4,5,6,7,8,9]，若找8
先将a[(0+7)/2]=a[4]=5与8比较，8大，所以8肯定在下标4-7内。
再将a[(4+7)/2]=a[5]=6与8比较，8大，所以8肯定在下标6-7内。
再将a[(6+7)/2]=a[6]=7与8比较，8大，所以8肯定在下标7内。

分块查找

又称索引顺序查找，是上述两个查找的结合，性能介于两者之间。

每个块可以无序，但是关键码（即最大值）必须从左到右由小到大。

步骤：

1. 选取各块的最大关键码构成一个索引表；
2. 对索引表进行两种选一查找方法，以确定在哪一块中；
3. 对已确定的块进行顺序查找。

二叉排序树