数据结构 9.1.2有序表的查找 折半查找：每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表。 算法实现：设表长为n,Iow、high和mid分别 指向待查元素所在区间的上界、下界和中点，k为 给定值。 初始时，令low=1,high=n, mid=L(Iow+high)/2。 让k与mid指向的记录比较： 若k=r[mid].key,查找成功。 若k<r[mid].key,则high=mid-1。 若k>r[mid].key,则low=mid+1。 重复上述操作，直至Iow>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 1 2 3 ￥ 6 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 lowmid high m
数据结构 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 2 4■ 5 6 7 8 9 10 11 51319 2137 566475 8088 92 low mid high 吉扇 9 10 19 高品64 75 80 88克 low mid high 日品高1高品 2 3 4 038站 9 645 low mid high 8 664 9 580 low high mid 2 3 4 5 61 7 d 9 1011 5 13 19 21 37 56 64 75 80 88 92 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
数据结构 判定树 为了分析二分查找的性能，可以用二叉树来描述二分 查找过程：树中每个结点表示表中一个元素，结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点，左子区间和右子区间分别作为根的左子 树和右子树，左子区间和右子区间再按此方法类推， 由此得到的二叉树称为二分查找的判定树。 日T吊37品64$08然克 3 891011 判定树： 10 8 找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，不在树上
数据结构 索引顺序表查找一分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针。 m
数据结构 tjm 索引顺序表查找——分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针