数据结构与算法分析之查找技术(ppt 75页)

数据结构与算法分析之查找技术目录：
1.1、顺序查找
1.2、有序表的对分查找
1.3、分块查找
1.4、二叉排序树查找
1.5、hashing技术

 

数据结构与算法分析之查找技术内容提要：
有序表的对分查找：
设有序线性表的长度为n，被查元素为x。
将x与线性表的中间项进行比较：
若中间项的值等于x，则说明查到，查找结束；
若x小于中间项的值，则在线性表的前半部分（即中间项
以前的部分）以相同的方法进行查找；
若x大于中间项的值，则在线性表的后半部分（即中间项
以后的部分）以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0(说明线性
表中没有这个元素)为止。
在最坏情况下，对分查找只需要比较log2n次，
而顺序查找需要比较n次。

..............................