顺序查找、折半查找、分块查找算法适合的场合。
-
顺序查找：顺序存储或链式存储的静态查找表均可。
-
折半查找（二分查找）：采用顺序存储结构的有序表。
-
分块查找（索引顺序查找 ）：分块有序表。
如果线性表既要快速查找又经常动态变化，要选择什么查找算法？
如果线性表既要快速查找又经常动态变化，则可采用分块查找。
分块查找是一种对大规模数据进行查找的有效方法。它将数据分为若干个块，每个块内部的数据可以是无序的，但是块与块之间是有序的。这样，当需要查找一个元素时，我们可以先确定它所在的块，然后在这个块内进行顺序查找。这样，查找的时间复杂度可以大大降低。
当线性表经常动态变化时，分块查找也有优势。因为当插入或删除元素时，只需要更新相应的块，而不需要对整个线性表进行排序，这样可以大大提高插入和删除的效率。
如何通过折半查找判定树求等概率时查找成功和不成功的平均查找长度ASL？
-
查找成功时，走一条从根结点到与该记录相应的结点的路径与给定值比较的次数恰等于该结点所在层次数。
-
查找不成功时，走一条从根结点到外部结点的路径与给定值比较的次数等于该路径上的内部结点个数。
如果有序表的长度为n，则外结点一定有n+1个（n+1个空链域）。某结点所在的层数就是即将要比较的次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。
各种查找算法的平均时间复杂度。
