课程名称：数据结构第15周，第15讲次摘要第九章查找授课题目（章、节）第一节查找的基本概念第二节静态查找【目的要求】通过本讲课程的学习，理解查找的基本概念，掌握在无序序列、有序序列中查找的方法，了解索引结构。【重点】理解基本概念（平均查找长度），掌握在有序序列中查找的方法。【难点】分析查找算法的平均查找长度。内容【本讲课程的引入】现实生活中，查找几乎无处不在，特别是现在的网络时代，万事离不开查找，小到文档内文字的搜索，大到INTERNET上的搜索，查找占据了我们上网的大部分时间。这一次课我们就开始学习关于查找的一些相关概念，以及查找的常用算法。【本讲课程的内容】9.1查找的基本概念（1）查找：查询特定元素是否在（数据元素集合）表中的过程。(2)查找成功：若表中存在特定元素，称查找成功，应输出该记录（3）查找不成功：否则，称查找不成功（也应输出失败标志或失败位置）：（4）静态查找：只查找，不改变数据元素集合内的数据元素。（5）动态查找：既查找，又改变（增减）集合内的数据元素。(6)关键字：记录中某个数据项的值，可用来识别一个记录（7）主关键字：可以唯一标识一个记录的关键字（8）次关键字：别若于记录的关键字讨论：讨论1：查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。讨论2：对查找表常用的操作有哪些？》查询某个“特定的”数据元素是否在表中，》查询某个“特定的”数据元素的各种属性；》在查找表中插入一元素：》从查找表中删除一元素。讨论3：有哪些查找方法？针对静态查找表和动态查找表的查找方法是有所不同的。9.2静态查找9.2.1在无序序列中查找在一个无序序列中查找某个数据元素是否存在的算法思想是：从数组的一端开始，用给定数据元素逐个和数组中各数据元素比较，若在数组中查找到要查找的数据元素，则查找成功：否则查找失败。在无序序列中查找某个数据元素是否存在的函数设计如下：public static int seqSeach(int a, int elem)(//在数组a中顺序查找数据元素elem是否存在。查找成功返回该元素的下标：失败返回
课程名称：数据结构 第 15 周，第 15 讲次 摘 要 授课题目（章、节） 第九章 查找 第一节 查找的基本概念 第二节 静态查找 【目的要求】通过本讲课程的学习，理解查找的基本概念，掌握在无序序列、有序序列中查找的方法，了解 索引结构。 【重 点】理解基本概念（平均查找长度），掌握在有序序列中查找的方法。 【难 点】分析查找算法的平均查找长度。 内 容 【本讲课程的引入】现实生活中，查找几乎无处不在，特别是现在的网络时代，万事离不 开查找，小到文档内文字的搜索，大到 INTERNET 上的搜索，查找占据了我们上网的大部分 时间。这一次课我们就开始学习关于查找的一些相关概念，以及查找的常用算法。 【本讲课程的内容】 9.1 查找的基本概念 (1) 查 找:查询特定元素是否在(数据元素集合)表中的过程。 (2)查找成功:若表中存在特定元素，称查找成功，应输出该记录. (3)查找不成功:否则，称查找不成功（也应输出失败标志或失败位置）. (4)静态查找:只查找，不改变数据元素集合内的数据元素。 (5)动态查找:既查找，又改变（增减）集合内的数据元素。 (6)关键字:记录中某个数据项的值，可用来识别一个记录. (7)主关键字:可以唯一标识一个记录的关键字. (8)次关键字:别若干记录的关键字. 讨论： 讨论 1：查找的过程是怎样的？ 给定一个值 K，在含有 n 个记录的文件中进行搜索，寻找一个关键字值等于 K 的记录， 如找到则输出该记录，否则输出查找不成功的信息。 讨论 2：对查找表常用的操作有哪些？ ➢ 查询某个“特定的”数据元素是否在表中； ➢ 查询某个“特定的”数据元素的各种属性； ➢ 在查找表中插入一元素； ➢ 从查找表中删除一元素。 讨论 3：有哪些查找方法？ 针对静态查找表和动态查找表的查找方法是有所不同的。 9.2 静态查找 9.2.1 在无序序列中查找 在一个无序序列中查找某个数据元素是否存在的算法思想是：从数组的一端开始，用 给定数据元素逐个和数组中各数据元素比较，若在数组中查找到要查找的数据元素，则查 找成功；否则查找失败。 在无序序列中查找某个数据元素是否存在的函数设计如下 ： public static int seqSeach(int[] a, int elem){ //在数组 a 中顺序查找数据元素 elem 是否存在。查找成功返回该元素的下标；失败返回
-1int n = a.length;int i=o;while(i< n && a[i] !=elem) i++;if(i==n) return -l:if(a[i] == elem) return i;9.2.2在有序序列中查找1、顺序查找有序数组中的顺序查找函数如下：public static int orderSeqSearch(int[J a, int elem)(int n = a. length;int i=o;while(i<n &a[i]<elem)i++;if(i=-n) return -l:if(a[i] =- elem) return i;else return -l;设要查找的数据元素在数据元素集合中出现的概率均相等，则有序序列的顺序查找算法查找成功时的平均查找长度ASL成功为：ASL成功=（1+n）/2查找失败时的平均查找长度ASL失败为：ASL失败=（1+n）/22、二分查找（又称折半查找）（1）算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至前半部内查找：再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。(2）二分查找算法二分查找非递归算法：public static intbiSearch(int[)a,int elem)(int n = a.length:int low = 0, high = n - l, mid;while(low <= high)(mid =(low+ high)/2:if(a[mid] == elem) return mid;else if(a[mid]) < elem) low=mid +1;else high =mid-l;return -l;二分查找递归算法public static int biSearch(int[ a,int x, int low, int high)(int mid;//查找不成功if(low >high) return -l;
-1 int n = a.length; int i = 0; while(i < n && a[i] != elem) i++; if(i==n) return -1; if(a[i] == elem) return i; } 9.2.2 在有序序列中查找 1、顺序查找 有序数组中的顺序查找函数如下： public static int orderSeqSearch(int[] a, int elem){ int n = a.length; int i = 0; while(i < n && a[i] < elem) i ++; if(i==n) return -1; if(a[i] == elem) return i; else return -1; } 设要查找的数据元素在数据元素集合中出现的概率均相等，则有序序列的顺序查找算法查 找成功时的平均查找长度 ASL 成功为： ASL 成功＝（1＋n）/2 查找失败时的平均查找长度 ASL 失败为： ASL 失败＝（1＋n）/2 2、二分查找（又称折半查找） (1) 算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将 key 与正 中元素相比，若 key 小，则缩小至前半部内查找；再取其中值比较，每次缩小 1/2 的 范围，直到查找成功或失败为止。 (2) 二分查找算法 二分查找非递归算法 ： public static int biSearch(int[] a, int elem){ int n = a.length; int low = 0, high = n - 1, mid; while(low <= high){ mid = (low + high)/2; if(a[mid] == elem) return mid; else if(a[mid] < elem) low = mid + 1; else high = mid - 1; } return -1; } 二分查找递归算法 public static int biSearch(int[] a, int x, int low, int high){ int mid; if(low > high) return -1; //查找不成功
mid=(low+high)/2:if(x == a[midj) return mid;//查找成功else if(x<a[mid])1/在上半区查找return biSearch(a,x,low,mid-1);elsereturnbiSearch(a，x，mid+1，high)；//在下半区查找A（3）折半查找算法性能评价1hn+1i.-2i-1ASL=-log2(n+1)-1=log2nnn分析：假设数据元素个数n恰好是满二叉树时的结点个数，这样在二叉树第i层上总共有2i-1个结点（设二叉树的根结点所在层数为1），查找该层上的每个结点需要进行的比较次数等于该结点所在层的深度。9.2.3分块查找（索引）（1）思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址。（2）分块查找过程：①对索引表可以使用折半查找法也使用顺序查找（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；（3）查找效率ASL分析：（A）若索引表查找使用折半查找法n、.s+ln+1ASLh.=log2（）+(logn≤ASL722s(B)若索引表查找使用顺序查找数据元素个数为n，主表中每块的长度为s，索引表长度m=n/s，则整个查找算法的平均查找长度为：s2+2s+nASL=m+-m+$+1=222s2当s=n%时，ASL取最小值n%+1，即当采用顺序查找确定块时，应将各块中的记录数选定为n%。9.2.4三种查找算法的比较三种查找方法比较如下：1.就平均查找长度而言，折半查找的平均长度最小，分块查找次之，顺序查找最大。2.就表的结构而言，顺序查找对有序表、无序表均可适用，折半查找仅适用于有序表，而分块查找要求表中元素至少是分块有序的。3.就表的存储结构而言，顺序查找和分块查找适用于顺序表和链表两种存储结构，而折半查找只使用于以顺序表作为存储结构的表。【本讲课程的小结】这一次课我们主要讨论了静态查找，静态查找问题不需要考虑数据的插入和删除，一般采用顺序存储结构，查找的方法比较简单
mid = (low + high) / 2; if(x == a[mid]) return mid; //查找成功 else if(x < a[mid]) return biSearch(a, x, low, mid - 1); //在上半区查找 else return biSearch(a, x, mid + 1, high); //在下半区查找 } （3）折半查找算法性能评价 分析：假设数据元素个数 n 恰好是满二叉树时的结点个数，这样在二叉树第 i 层上总共有 2i-1 个结点（设二叉树的根结点所在层数为 1），查找该层上的每个结点需要进行的比较次 数等于该结点所在层的深度。 9.2.3 分块查找（索引） （1）思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一 块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表 中还要包含每个子表的起始地址。 （2）分块查找过程： ① 对索引表可以使用折半查找法也使用顺序查找 （因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序 表）； （3）查找效率 ASL 分析： （A）若索引表查找使用折半查找法 (B)若索引表查找使用顺序查找 数据元素个数为 n，主表中每块的长度为 s，索引表长度 m=n/s，则整个查找算法的平均查 找长度为： 当 s=n ½时，ASL 取最小值 n ½+1，即当采用顺序查找确定块时，应将各块中的记录数选定 为 n ½ 。 9.2.4 三种查找算法的比较 三种查找方法比较如下： 1.就平均查找长度而言，折半查找的平均长度最小，分块查找次之，顺序查找最大。 2.就表的结构而言，顺序查找对有序表、无序表均可适用，折半查找仅适用于有序表，而 分块查找要求表中元素至少是分块有序的。 3.就表的存储结构而言，顺序查找和分块查找适用于顺序表和链表两种存储结构，而折半 查找只使用于以顺序表作为存储结构的表。 【本讲课程的小结】这一次课我们主要讨论了静态查找，静态查找问题不需要考虑数据的 插入和删除，一般采用顺序存储结构，查找的方法比较简单。 n n n n i n ASL h i i 2 2 1 1 log ( 1) 1 log 1 2 1 + − + = = = − ) 2 1 (log 2 1 log ( ) 2 2 + + + n n ASL s s n ASLb s b s s m s m s s s n ASL 2 2 1 2 2 1 2 1 2 + + + = + = + + + =
【本讲课程的作业】已知一个有序表为（12，18，20，25，29，32，40，62，83，90，95，98），当二分查找值为29和90的元素时，分别需要多少次比较才能查找成功？若采用顺序查找时，分别需要多少次比较才能查找成功？
【本讲课程的作业】 已知一个有序表为（12，18，20，25，29，32，40，62，83，90，95，98），当二分查找值 为 29 和 90 的元素时，分别需要多少次比较才能查找成功？若采用顺序查找时，分别需要 多少次比较才能查找成功？