有序表的查找 顺序表的查找算法简单,但平均查找长 度较大,不适用于表长较大的查找表。 若以有序表表示静态查找表,则查找过 程可以基于“折半”进行。 折半查找 查找过程:每次将待查记录所在区间缩小一半。 适用条件:采用顺序存储结构的有序表
顺序表的查找算法简单，但平均查找长 度较大，不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过 程可以基于“折半”进行。 §有序表的查找 折半查找 查找过程：每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表
折半查找算法实现 1设表长为n,low、high和md分别指向待查 元素所在区间的上界、下界和中点k为给定 值 2初始时,令 low=1, high=n, mid-dow+high)/2] 让k与mid指向的记录比较 若k=r| mid key,查找成功 若k<r| mid. key,则high=mid-1 若k>r| mid key,则low=mid+1 3重复上述操作,直至ow>high时,查找失 败
1.设表长为n，low、high和mid分别指向待查 元素所在区间的上界、下界和中点,k为给定 值。 2.初始时，令 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 3.重复上述操作，直至low>high时，查找失 败。 折半查找算法实现
例如key=21的查找过程 找21 1234567891011 例 13192137566475808892 low mid high 1234567891011 513192137566475808892 OW d high 234 678910 513192137566475808892 low mid high low指示查找区间的下界 high指示查找区间的上界; mid=(low+high)/2
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 找21 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 例如 key =21 的查找过程 low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2
例key=70的查找过程〈找7 3 78910 513192137566475808892 Ow d high 234567891011 513192137566475808892 Ow mid high 123 567891011 513192137566475808892 low mid high 234567891011 513192137566475808892 low higl h mid
例key =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 找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 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
1234567891011 513192137566475808892 high low 12345678 513192137566475808892 当下界low大于上界high时,则说明表中 没有关键字等于Key的元素,查找不成功
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 当下界low大于上界high时，则说明表中 没有关键字等于Key的元素，查找不成功