基于有序顺序表的折半查找 设n个数据对象存放在一个有序顺序表中, 并按其关键字值从小到大(或从大到小) 排好序 n原理:折半查找时,每次都先求出位于查 找区间正中的对象的下标mid,用其关键 字与给定值x比较,然后根据比较结果将 查找区间缩小一半,直至找到被查找对象 第16页
基于有序顺序表的折半查找 ◼ 设n个数据对象存放在一个有序顺序表中， 并按其关键字值从小到大（或从大到小） 排好序。 ◼ 原理：折半查找时, 每次都先求出位于查 找区间正中的对象的下标mid，用其关键 字与给定值x比较，然后根据比较结果将 查找区间缩小一半，直至找到被查找对象。 第 16 页
折半查找算法 (设数据按关键字从小到大有序排列) 1 Element[mid]. key==×查找成功 2 Element[mid]. key>×把查找区间缩小为 表的前半部分,继续折半查找; 3 Element[mid]. key<x把查找区间缩小为 表的后半部分,继续折半查找; 如果查找区间缩小到一个对象,且仍 未找到想要查找的对象,则查找失败 第17页
折半查找算法 （设数据按关键字从小到大有序排列） 1.Element[mid].key==x 查找成功； 2.Element[mid].key>x 把查找区间缩小为 表的前半部分，继续折半查找； 3.Element[mid].key<x 把查找区间缩小为 表的后半部分，继续折半查找； ➢如果查找区间缩小到一个对象，且仍 未找到想要查找的对象，则查找失败。 第 17 页
例如:key=64的查找过程如下 SL length SLelem 0513192137566475808892 01234567891011 OW high mid md=(loWw+high)/2」(向下取整) LoW指示查找区间的下界 high指示查找区间的上界 第18页
第 18 页 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 SL.elem SL.length 例如: key=64 的查找过程如下 low high mid mid mid mid = (low+high)/2 （向下取整） Low 指示查找区间的下界 high 指示查找区间的上界 low high
012345678 搜索6-10134681012 low mid high 1)low=0high=8,mid=4;由于 5678 Elem [mid]<Key因此,low= 68110 12 mid+1=5; low 6 high (2)mid=6由于Eem[mid}Key 因此high=md-1=5; (3)mid=5, Elem[mid]-Key因此 56 查找成功 6 low mid high 查找成功的例子 第19页
第 19 页 查找成功的例子 6 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 搜索 low mid 6 high 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6 (1) low=0,high=8,mid=4;由于 Elem[mid]<Key, 因此，low＝ mid+1=5; (2) mid=6,由于Elem[mid]>Key, 因此, high=mid-1=5; (3)mid=5, Elem[mid] =Key,因此 查找成功
012345678 搜索5[-10134|6|8|1012 Ow nid 5 high 1)low=0high=8,mid=4;由于 5678 Elem [mid]<Key因此,low= 61810|12 mid+1=5; (2)mid=6由于Eem[mid}Key low mid 5 high 因此high=md-1=5; (3md=5由于Elem[mid]Key因 56 此high=md-1=4.由于此时 high<ow因此查找失败 low mid high 查找失败的例子 第20页
第 20 页 查找失败的例子 5 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 搜索 low mid 5 high 6 8 10 12 5 6 7 8 low mid high 5 6 5 low mid high 5 (1) low=0,high=8,mid=4;由于 Elem[mid]<Key, 因此，low＝ mid+1=5; (2) mid=6,由于Elem[mid]>Key, 因此, high=mid-1=5; (3)mid=5,由于Elem[mid] >Key,因 此, high=mid-1=4. 由于此时 high<low,因此查找失败