数据结构 9.12有序表的查找 折半查找每次将待查记录所在区间缩小一半。 适用条件:采用顺序存储结构的有序表。 算法实现:设表长为n,loW、hgh和md分别 指向待查元素所在区间的上界、下界和中点,k为 给定值。 初始时,令lowW=1,hgh= mid=L(ow +high)/2] 让k与md指向的记录比较: 若k=r[mid]key,查找成功。 若k<r[mid]key,则high=mid-1 若k>r[mid]key,则ow=mid+r° 重复上述操作,直至low>high时,查找失败。 算法参见P220
数据结构 tjm 9.1.2 有序表的查找 折半查找:每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表。 算法实现：设表长为n，low、high和mid分别 指向待查元素所在区间的上界、下界和中点，k为 给定值。 初始时，令low=1，high=n， mid=(low+high)/2。 让k与mid指向的记录比较： 若k=r[mid].key，查找成功。 若k<r[mid].key，则high=mid-1。 若k>r[mid].key，则low=mid+1。 重复上述操作，直至low>high时，查找失败。 算法参见P220
数据结构 例:找21 234567891011 513192137566475808892 low mid 1234567891011 513192137566475808892 Ow mid high 2345678 513192137566475808892 lowmid high
数据结构 tjm 例：找21 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowmid high
数据结构 例:找70 375664 188 low m d high 1319 37566475808892 ml d bt舒6号想 low mid high 3192137566475808892 low high mid 234 011 513192137566475808892 high low
数据结构 tjm 例：找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low
数据结构 判定树 为了分析二分查找的性能,可以用二叉树来描述二分 查找过程:树中每个结点表示表中一个元素,结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点,左子区间和右子区间分别作为根的左子 树和右子树,左子区间和右子区间再按此方法类推, 由此得到的二叉树称为二分查找的判定树。 i312137566475|80892 判定树: 5(8①D 找21:比较次数=3,在树上 找85:比较次数=3,不在树上
数据结构 tjm 判定树 为了分析二分查找的性能，可以用二叉树来描述二分 查找过程：树中每个结点表示表中一个元素，结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点，左子区间和右子区间分别作为根的左子 树和右子树，左子区间和右子区间再按此方法类推， 由此得到的二叉树称为二分查找的判定树。 2 5 8 11 1 4 7 10 3 9 判定树： 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 21：比较次数 = 3，在树上 找 85：比较次数 = 3，不在树上
数据结构 索引顺序表查找—分块查找 查找过程:将表分成几块,块内无序,块间有 序;先确定待查记录所在块,再在块内查找。 适用条件:分块有序表。 算法实现: 用数组存放待查记录。 建立索引表,每个索引表结点含有最大关键字 城和指向本块第一个结点的指针
数据结构 tjm 索引顺序表查找——分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针