顺序查找的效率 对含有n个记录的表，ASL=∑p,c, i=l T(n)=O(n) 设表中每个元素的查找概率相等p, n 则AM=∑pc,=i= n(n+1) n+1 i= i1 n 2 2
顺序查找的效率 2 1 2 1 1 ( 1) 1 1 1 n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等 n i i i n ASL p c 1 对含有 个记录的表， T(n)=O(n)
9.1. 2有序表的查找 折半查找，也称二分查找， 是一种高效率的查找方 法。但要求表中元素必须按关键字有序（升序或降 序) ★查找过程：每次将待查记录所在区间缩小一半 ★适用条件：采用顺序存储结构的有序表
折半查找，也称二分查找，是一种高效率的查找方 法。但要求表中元素必须按关键字有序(升序或降 序)。 «查找过程：每次将待查记录所在区间缩小一半 «适用条件：采用顺序存储结构的有序表 9.1.2 有序表的查找
9.1.2有序表的查找 ★算法实现 冬设表长为n,Iow、high和mid分别指向待查元 素所在区间的上界、下界和中点，k©y为给定值 冬初始时，令low=1,high=n,mid=L(low+high)M2 必让key与mid指向的记录比较 若key==ST.elem[mid.key,查找成功 若key<ST.elem[mid.key,则high=mid-1 ●若key>ST.elem[mid.key,则low=mid+1 冬重复上述操作，直至Iow>high时，查找失败
«算法实现 v设表长为n，low、high和mid分别指向待查元 素所在区间的上界、下界和中点,key为给定值 v初始时，令low=1,high=n,mid=(low+high)/2 v让key与mid指向的记录比较 l若key==ST.elem[mid].key，查找成功 l若key< ST.elem[mid].key ，则high=mid-1 l若key> ST.elem[mid].key ，则low=mid+1 v重复上述操作，直至low>high时，查找失败 9.1.2 有序表的查找
举例说明(1) 找key=21 1234567 8 9 1011 51319 2137 56 64 75 80 88 92 ↑t↑ low high mid
举例说明(1) low 找key=21 5 1 13 2 19 3 21 4 37 5 56 6 64 7 75 8 80 9 88 10 92 11 mid mid high mid low high
举例说明（②） 找key=70 12345678 91011 51319213756 647580 88 92 high low
low 找key=70 5 1 13 2 19 3 21 4 37 5 56 6 64 7 75 8 80 9 88 10 92 11 mid low mid high mid 举例说明(2) low high mid high