二分法检索算法 ∥/代码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 }