顺序检索性能分析 顺序检索平均检索长度 每个关键码是等概率的,Pi=1/n 设检索成功的概率为p,检索失败的概率 q=(1-p ASL +1 +(1-p)(n+1) ∑i (n+1)(1-P/2) 失败时都需要比较n+1次(设置了一个 (n+1)/2<AsI 叔新有,盘 张 顺序检索优缺点 9.1.2二分检索法 ■优点:插入元素可以直接 将任一元素 dataList[i]Key与给定值K 加在表尾⊙(1) 三种情况: (1)Key=K,检寰成功,返回 dataList m缺点:检索时间太长e(n) (2)Key>K,若有则一定排在 dataList[Ol前 (3)Key<K,若右则一定排在 dataList们后 缩小进一步检索的区间 订恤 张铭趣 张帖 二分法检索图示 二分法检索算法 23|4|5678 ype> int Bin Search 17|82235|516088 ector<Item<Type>*>& dataList,int length, Type k) while(low<=high) mid=(low+high)/2 if (k<data List[mid]->getKeyo) 检索关键码181ow=1high=9K=18 区间 else if (k>dat low mid+1 else return mid;//成功返回位置 第二次:mid=2;aray[2]=17(18 turn0;//检紫失败,返回0 =1818 张帖兽3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 顺序检索性能分析 „ 检索成功 假设检索每个关键码是等概率的，Pi = 1/n „ 检索失败 假设检索失败时都需要比较n+1次（设置了一个 监视哨） Pi n i i n n n i i n i n i n ·() () − = − ∑ = − = − ∑ = = + = ∑ 0 1 1 0 1 1 2 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 顺序检索平均检索长度 „ 假设检索成功的概率为p，检索失败的概率 为q=(1-p) „ （n+1)/2 < ASL < (n+1) 1 A SL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p qn n p pn n p + = ⋅ +⋅ + + = ⋅ +− + =+ − 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 顺序检索优缺点 „优点：插入元素可以直接 加在表尾Θ(1) „缺点：检索时间太长Θ(n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 9.1.2 二分检索法 „ 将任一元素dataList[i] .Key与给定值K 比较 „ 三种情况： （1）Key = K，检索成功，返回dataList[i] （2）Key > K，若有则一定排在dataList[i]]前 （3）Key < K，若右则一定排在dataList[i]后 „ 缩小进一步检索的区间 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 二分法检索算法 template <class Type> int BinSearch (vector<Item<Type>*>& dataList,int length,Type k){ int low=1, high=length, mid; while (low<=high) { mid=(low+high)/2; if (k<dataList[mid]->getKey()) high = mid-1; //右缩检索区间 else if (k>dataList[mid]->getKey()) low = mid+1; //左缩检索区间 else return mid; //成功返回位置 } return 0; //检索失败，返回0 } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 检索关键码18 low=1 high=9 K=18 第一次：mid=5; array[5]=35>18 high=4; (low=1) 第二次：mid=2; array[2]=17<18 low=3; (high=4) 第三次：mid=3; array[3]=18=18 mid=3；return 8 二分法检索图示 35 1 2 3 45 6 7 8 9 15 22 51 60 88 93 low mid high 17 18