9.1.2二分检索法 将任一元素 datalist[i]Key与给定值K 比较 三种情况: (1)Key=K,检索成功,返回 datalist[] (2)Key>K,若有则一定排在 data List[]前 (3)Key<K,若右则一定排在 dataList们]后 缩小进一步检索的区间 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 16
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 9.1.2 二分检索法 将任一元素dataList[i] .Key与给定值K 比较 三种情况： （1）Key = K，检索成功，返回dataList[i] （2）Key > K，若有则一定排在dataList[i]]前 （3）Key < K，若右则一定排在dataList[i]后 缩小进一步检索的区间
二分法检索算法 template <class Type> int Bin Search (vector <Item <Type>*>& data List, int length, Type k)i int low= 1, high=length mid; while (low<=hight id=(lowthigh/2i if (k<dataList[mid]->getKeyo) hgh=mid-1;/右缩检索区间 else if (k>data List[mid]->getKeyo) loW=mid+1;//左缩检索区间 else return mid;//成功返回位置 return o;//检索失败,返回0 k 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 17
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 }
二分法检索图示 123456789 15171822|35|51608893 mI high 检索关键码181ow=1high=9K=18 第一次:mid=5;aray[5]=3518 high=4,(low=1 第二次:mid=2; array[2]=17<18 low=3; (high=4) 第三次:mid=3; array[3]=18-18 mid=3: return 8 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 18
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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
二分法检索性能分析 最大检索长度为 35 log,(n+D 7 17 60 ■失败的检索长度是 停止在内部叶结点(5 og2(n+1) )1 或 4(22 93 Llog2(n+1)」 停止在外部空结点,则加1 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 19
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 二分法检索性能分析 最大检索长度为 失败的检索长度是 停止在内部叶结点 或 停止在外部空结点，则加1 ⎣ ⎦ log（2 n + 1） ⎡ ⎤ log（2 n + 1） 15 18 22 51 7 8 9 2 1 3 4 88 60 93 35 17 5 ⎡ ⎤ log（2 n +1）
二分法检索性能分析(续) 成功的平均检索长度为: ASL=-(∑ n+1 1092 n+1)-1 ≈log,(n+1)-1 (n>50) 优缺点 优点:平均与最大检索长度相近,检索速度快 缺点:要排序、顺序存储,不易更新(插/删) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 20
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 二分法检索性能分析（续） 成功的平均检索长度为： (n > 50) 优缺点 优点：平均与最大检索长度相近，检索速度快 缺点：要排序、顺序存储，不易更新(插/删) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n − = ⋅ ∑ = + = + − ≈ +−