91.2二分检索法 有序表:线性表中所有数据元素 按关键码值递增(或递减)的次 序排列 在有序表的存储表示下,检索可 以用效率更高的二分检索法实现 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 9.1.2 二分检索法 ◼ 有序表：线性表中所有数据元素 按关键码值递增（或递减）的次 序排列 ◼ 在有序表的存储表示下，检索可 以用效率更高的二分检索法实现
9.1.2二分法检索 有序表中所有元素按关键码值递增(或递减)的次序 排列 将表中任一元素 data list[i]的关键码值Key与给定 值K比较, 可根据三种比较结果区分出三种情况(以递增为例) (1)Key=K,检索成功, dataList[订]即为待查元素 (2)Key>K,说明待查元素若在表中,且一定排在 datalist[i]之前 (3)Key<K,说明待查元素若在表中,且一定排在 dataList[之后 因此,在一次比较之后,若没有找到待查元素(即情 况1未出现),则可根据比较结果缩小进一步检索的 区间 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 9.1.2 二分法检索 ◼ 有序表中所有元素按关键码值递增（或递减）的次序 排列 ◼ 将表中任一元素dataList[i]的关键码值Key与给定 值K比较， ◼ 可根据三种比较结果区分出三种情况（以递增为例）： （1） Key = K，检索成功，dataList[i]即为待查元素 （2） Key > K，说明待查元素若在表中，且一定排在dataList[i]]之前 （3） Key < K，说明待查元素若在表中，且一定排在dataList[i]之后 ◼ 因此，在一次比较之后，若没有找到待查元素（即情 况1未出现），则可根据比较结果缩小进一步检索的 区间
二分法检索算法 ∥/代码9-3二分检索算法 template <class Type> int BinSearch vector<Item<Type>*>& data int length, Type ki //low,high分别记录数组首尾位置 int low=1 high=length, mid while (low<=hight mid=(low+high)/2i if (k<dataList[mid]->getKeyo high mid-1 //右缩检索区间 else if (k>data List[mid]->getKey o) low= mid+1i /左缩检索区间 else return mid: /检索成功,返回元素位置 return o: //检索失败,返回0 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 二分法检索算法 ◼ //代码9-3 二分检索算法 template <class Type> int BinSearch (vector<Item<Type>*>& dataList,int length,Type k) { //low, high分别记录数组首尾位置 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 151718223551608893 low high 检索关键码18。10w=1;high=9;K=18 第一次:mid=5; array[5j=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 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 检索关键码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 二分法检索图示
二分法检索性能分析 5 35 60 15 18 51 88 4(22 93 最大检索长度为g2(n+1 失败的检索长度是「og2(n+1)1 或log2(n+1) 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 二分法检索性能分析 ◼ ◼ 最大检索长度为 ◼ 失败的检索长度是 或 log（2 n +1） log（2 n +1） log（2 n +1）