查找
- 分块查找法要求将列表组织成以下索引顺序结构：
首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。 每块中元素任意排列，即块内无序，但块与块之间有序。 构造一个索引表。==其中每个索引项对应一个块并记录每块的起始位置，和每块中最大 关键字（或最小关键字）==。索引表按关键字有序排列。 - 二分查找即折半查找，必须 ==有序顺序存储==表。
- 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度：
最好的情况：目标在第一个,一次找到 ····· 最坏的情况：目标在最后一个,n次找到 那么： 平均长度： （1+2+···+n）/n =(n(n+1)/2)/n ===(n+1)/2== - 平均查找速度：==顺序 <分块 <折半 <哈希==
- 分块查找是==折半查找和顺序查找==的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。==分块查找步骤==：索引表查找长度+分块查找长度
- 二叉查找树的查询速度取决于==树的深度==，==相同结点数深度最小的是平衡二叉树==。
- 构成折半查找中关键字比较序列判断==是否满足二叉排序树==。
- 选择问题的复杂度下界。找最大元素比较次数的下界是：==n-1== 找第二大元素比较次数的下界是：==n+logn-2==
