二分检索 在,个有序序列中,查找给定的元素,通常使用二 分检索较为高效 二分査找是分治算法中比较特殊的一类 分:将有序序列分为相等的两半 治:比较需要查找元素的关键码和序列中位数比较 令如果中位数较小,则继续在较大的半段中继续查找 如果中位数较大,则在较小的半段中查找 如果相等,则返回中位数地址,查找成功 ≤合:返回在自序列中查找的结果即可 二分查找的时间复杂度为O(ogn) 16
16 二分检索 ❖ 在一个有序序列中，查找给定的元素，通常使用二 分检索较为高效 ❖ 二分查找是分治算法中比较特殊的一类 分：将有序序列分为相等的两半 治：比较需要查找元素的关键码和序列中位数比较 ❖ 如果中位数较小，则继续在较大的半段中继续查找 ❖ 如果中位数较大，则在较小的半段中查找 ❖ 如果相等，则返回中位数地址，查找成功 合：返回在自序列中查找的结果即可 ❖ 二分查找的时间复杂度为O(log n)
二分检索法 令将任元素 gataglisti6Key与拾劍值K比较 种|2355160893 索 (2)Key>K,若有则一定排在 dataList]前 (3)Key<K,若右则一定排在 datalist后 令缩小进一步检索的区间 17
17 二分检索法 ❖ 将任一元素dataList[i] .Key与给定值K比较 三种情况： （1）Key = K，检索成功，返回dataList[i] （2）Key > K，若有则一定排在dataList[i]]前 （3）Key < K，若右则一定排在dataList[i]后 ❖ 缩小进一步检索的区间 35 1 2 3 4 5 6 7 8 9 15 17 18 22 51 60 88 93
关键码18low=1high=9 123456789 15171822|3551608893 O m high 第一次:1=1,h=9,mid=5; arrays]35>18 第二次:1=1,h=4,mid=2;aray[2}=17<18 第三次:3,h=4,mid=3; array3l=18=18 18
18 关键码18 low=1 high=9 35 1 2 3 4 5 6 7 8 9 15 22 51 60 88 93 low mid high 17 18 第一次：l=1, h=9, mid=5; array[5]=35>18 第二次：l=1, h=4, mid=2; array[2]=17<18 第三次：l=3, h=4, mid=3; array[3]=18＝18
二分法检索算法 template <class Type> int Bin Search(vector<Item<Type>*>& datalist, int length, Type kt int low=l, high=length, mid; while (low < high)( mid=(+high)/2; if (k< dataList mid]->getKeyo high mid-1 /右缩检索区间 else if(k> dataList(mid] ->getKeyo) low=mid+;∥左缩检索区间 else return mid; ∥成功返回位置 return0;/检索失败,返回0 19
19 二分法检索算法 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 }
二分法检索的递归算法1 tem plate<class elem> int binary( Elem array,intn,KeyK)t∥n为数组长度,K为待检值 int=-1: intr=n; // and r are beyond the bounds of array while(+1l=rt l Stop when I and r meet int i=(+r)/2; l/ Check middle of remaining subarray if (K< array r=i; ∥/ In left half if(K> array(I=i; lIn right half if (K= array [] return i; // Found it return UNSUCCESSFUL; /Search value not in array 20
20 二分法检索的递归算法1 template<class Elem> int binaryt(Elem array[], int n, Key K) { // n为数组长度, K为待检值 int l = -1; int r = n; // l and r are beyond the bounds of array while (l+1 != r) { // Stop when l and r meet int i = (l+r)/2; // Check middle of remaining subarray if (K < array[i]) r = i; // In left half if (K > array[i]) l = i; // In right half if (K = array[i]) return i; // Found it } return UNSUCCESSFUL; // Search value not in array }