1234567891011 513192137566475808892 判定树: 3 9 2)()(8①
例如key=64的查找过程如下 STlength STelem 0513192137566475808892 01234567891011 low high mid low指示查找区间的下界; high指示查找区间的上界; mid=( owthigh)2
0 5 1 3 1 9 2 1 3 7 5 6 6 4 7 5 8 0 8 8 9 2 0 1 2 3 4 5 6 7 8 9 1 0 1 1
折半查找举例:已知如下1个元素的有序表: (0513192137566475808892),请查找关键字为21 和85的数据元素 Lo指向待查元素d向特查元素所hig指向特查元素所在 所在区间的下界 在区间的中间位置 区间的上界 解:①先设定3个辅助标志:low,high,mnid, 显然有:mid=L(ow+high)2」 ②运算步骤 (1)oW=1,high11mid=6,待查范围是[1,11 (2)若 SLelem[m]key<key,说明key∈[mi+1hgh, 则令:low=mid+1重算md=L(ow+high)2 (3)若 STelem[mid]key>key,说明key∈[ow,md1, 则令:high=mid-;重算md; (4)若 STelem[ mid]key=key,说明查找成功,元素序号=mid 结束条件:(1)查找成功: STele[md]key=key (2)查找不成功: highlow(意即区间长度小于0)
int Search Bin( SSTable ST, Key Type kval low=l;high= STength;∥置区间初值 while(low <=high)i mid=(low high)/2 if (kval==STelem[mid].key return mid;∥找到待查元素 else if( kval STelem [mid]. key)) high=mid-1;∥继续在前半区间进行查找 else low=mid+1;∥继续在后半区间进行查找 return 0 ∥顺序表中不存在待查元素 ∥ Search Bin
讨论①若关键字不在表中,怎样得知和停止? 性能分新 典型标志是:当查找范围的上界<下界时停止查找 讨论②二分查找的效率(ASL) 1次比较就查找成功的元素有1个(2),即中间值 推2次比较就查找成功的元素有2个(2即4处(或3√4)处 导3次比较就查找成功的元素有4个(2即8处(或38)处 过4次比较就查找成功的元素有8个(2即16处(或M6)处 程 则第m次比较时查找成功的元素会有2m个; 为方便起见,假设表中全部n个元素=2m1个,此时就不讨论第m 次比较后还有剩余元素的情况了。 全部比较总次数为×2+2×21+3×22+4×23+m×2m1 2-1 ∑
m j j j 1 1 2