数据结构_第6章 查找.ppt

第六章;课程目标;体验;何谓查找 ;本章给大家介绍线性查找和折半查找 ;线性查找 ;要查找“2”的方法如下： 步骤1：与数组中第1个元素比较。2≠5，向下寻找 步骤2：与数组中第2个元素比较。2≠3，向下寻找 步骤3：与数组中第3个元素比较。2≠6，向下寻找 步骤4：与数组中第4个元素比较。2＝5，找到该数据 ;如果现在想找元素“7” 步骤1：与数组中第1个元素比较。7≠5，向下寻找 步骤2：与数组中第2个元素比较。7≠3，向下寻找 步骤3：与数组中第3个元素比较。7≠6，向下寻找 步骤4：与数组中第4个元素比较。7＝2，向下寻找 步骤5：与数组中第5个元素比较。7＝1，已找到最 后一个数据仍未找到，所以返回未找到数据。 ;线性查找的例子 public class LinearSearch { public boolean lSearch(int[] a,int key) { for(int i=0;ia.length;i++) { if(key==a[i]) { System.out.println(key+ 的位置 +i); return true; } } return false; } } ; 线性查找是查找方法中效率最低的一种。但是因为此方法简单而且对数据不用经过排序处理，所以在实际应用中还是被大量的用到。 下面一节给大家介绍一种效率更高的查找方法 ;折半查找 ;例如：int[] a={2,3,6,8,9,10,12,16}; ; 步骤1： 12a[middle]=8 左边界（left）=3+1=4、右边界（right）=7 标志位（middle）=(4+7)/2=5 步骤2： 12a[middle]=10 左边界（left）=4+1=5、右边界（right）=7 标志位（middle）=(5+7)/2=6 步骤3： 12=a[middle]=12 此时该数据已被找到，返回该数据的位置，也 就是标志位（middle） ; 上面的例子举的是数组中含有被查找的数据，那如果数组中没有所要找的数据，我们该怎么办呢？在什么时候结束查找呢？我们一起来看下面的例子： 还是以数组ａ为例。我们想查找“５” 则此时左边界（left）=0、右边界（right）=a.length-1=7、 标志位（middle）=（left+right）/2=（0+7）/2=3、 欲查找值（key）=12： ; 步骤１： 5a[middle]=8 左边界（left）=0、右边界（right）=3-1=2 标志位（middle）=(0+2)/2=1 步骤2： 5a[middle]=3 左边界（left）=1+1=2、右边界（right）=2 ??志位（middle）=（2+2）/2=2 步骤3： 5a[middle]=6 左边界（left）=2、右边界（right）=2 此时左边界=右边界，未能查找到数据 ;非递归方式查找 ;折半查找还可以用递归的方式来实现 ;拓展——二叉查找树 ;以下图为例 ;如果我们想找出节点序号为9的节点则： 步骤1：9先与根节点比较。94；向根节点的右子树查找。 步骤2：9与节点6比较。96；向节点6的右子树查找。 步骤3：9与节点7比较。97；；这时节点7没有子节点，查 找完毕，没有找到数据。 ;作业