二分法检索算法 template <class Type> int Bin Search (vector<item<Type>*>& dataList, int length, Type k)i int low=l, high=length, mid while (low<=high)i mid=(low+high)/2 if (k<dataList mid]->getKeyo) high=md-1;∥右缩检索区间 else if (kedatalistmid->getKeyo low=mid+1;∥左缩检索区间 else return mid ∥成功返回位置 return0;/检索失败,返回0 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二分法检索算法 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 }
关键码18low=1high=9 123456789 151718223551608893 low mid high 第一次:=1,h=9,mid=5; array5=35>18 第二次:=1,h=4,mid=2; array{2=17<18 第三次:=3,h=4,mid=3;aray3=18=18 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 关键码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
二分法检索性能分析 最大检索长度og2(n+1)1 失败的检索长度是 35 「log2(n+1) 17 60 或 log, (n+1) 15)(18)(51 88 在算法复杂性分析中 口logn是以2为底的对数 22 93 口其他底,算法量级不变 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二分法检索性能分析 ◼ 最大检索长度 ◼ 失败的检索长度是 或 ◼ 在算法复杂性分析中 ❑ log n是以2为底的对数 ❑ 其他底，算法量级不变 log（2 n +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 6
二分法检索性能分析(续) 成功的平均检索长度为: ASL、l (∑t2-1) ≈n+1og2(n+1)-1 ≈log2(n+1)-1(n>50) 优缺点 口优点:平均与最大检索长度相近,检索速度快 口缺点:要排序、顺序存储,不易更新(插/删 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二分法检索性能分析（续） ◼ 成功的平均检索长度为： (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 − = = + = + − + −
10.13分块检索 顺序与二分法的折衷 口既有较快的检索 口又有较灵活的更改 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1.3 分块检索 ◼ 顺序与二分法的折衷 ❑ 既有较快的检索 ❑ 又有较灵活的更改