数据结构（c语言版）（全套课件）.ppt

2 算法分析 不失一般性，设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=n-i+1 ； ◆ 查找成功时的平均查找长度ASL： ASL=∑ Pi?Ci= i=1 n ∑ (n-i+1)= i=1 n n ― 1 2 n+1 64 5 13 19 21 37 56 64 75 80 88 92 监视哨 查找64 0 1 2 3 4 5 6 7 8 9 10 11 p p p p p 比较次数=5 图9-1 顺序查找示例 ASL=∑ Pi?Ci= i=1 n 2 n+1 ∑ (n-i+1)+ i=1 n 2n 1 =3(n+1)/4 ◆ 包含查找不成功时：查找失败的比较次数为n+1，若成功与不成功的概率相等，对每个记录的查找概率为Pi=1/(2n)，则平均查找长度ASL： 9.2.2 折半查找(Binary Search) 折半查找又称为二分查找，是一种效率较高的查找方法。 前提条件：查找表中的所有记录是按关键字有序(升序或降序) 。 查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。 1 查找思想 用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。 ⑴ 取中间位置Mid：Mid=?(Low+High)/2? ； ⑵ 比较中间位置记录的关键字与给定的K值： ① 相等： 查找成功； ② 大于：待查记录在区间的前半段，修改上界指针： High=Mid-1，转⑴ ； ③ 小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ； 直到越界(Low>High)，查找失败。 2 算法实现 int Bin_Search(SSTable ST , KeyType key) { int Low=1，High=ST.length, Mid ; while (Low<High) { Mid=(Low+High)/2 ; if (EQ(ST. elem[Mid].key, key)) return(Mid) ; else if (LT(ST. elem[Mid].key, key)) Low=Mid+1 ; else High=Mid-1 ; } return(0) ; /* 查找失败 */ } 查找21 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low (a) 查找成功示例 3 算法示例 如图9-2(a)，(b)所示。 查找71 -5 13 17 23 38 46 56 65 78 81 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low -5 13 17 23 38 46 56 65 78 81 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low -5 13 17