它”?从上述查找思想可知,每进行一次关键字比较,区间数 目增加一倍,故称为二分(区间一分为二),而区间长 度缩小一半,故也称为折半(查找的范围缩小一半) 2.二分查找算法实现 int binsearch (node R[n+1], elemtype k i int low-l, high-n 入 while(low<-high) i int mid=(low +high)/2 取区间中点 if(R[mid]key==k) return mid;∥查找成功 else if(TImid. key>k) high=mid-1 在左子区间中查找 else low-mid+1;) ∥右子区间中查找 return 0; ∥找失败
从上述查找思想可知，每进行一次关键字比较，区间数 目增加一倍，故称为二分（区间一分为二），而区间长 度缩小一半，故也称为折半（查找的范围缩小一半）。 2．二分查找算法实现 int binsearch (node R[n+1], elemtype k) { int low=1, high=n; while (low<=high) { int mid=(low +high)/2; //取区间中点 if (R[mid].key= =k) return mid; //查找成功 else if (R[mid].key>k) high=mid-1; //在左子区间中查找 else low=mid+1; } //在右子区间中查找 return 0; } //查找失败
例如,假设给定有序表中关键字为 8,17,25,4468,7798,100,115,125,将查找K=17和K=120 的情况描述为图8-1及图8-2形式 817254468779810115125] low (a)初始情形 [8172544]684498100115125 high d (b)经过一次比较后的情形
例 如 ， 假 设 给 定 有 序 表 中 关 键 字 为 8,17,25,44,68,77,98,100,115,125，将查找K=17和K=120 的情况描述为图8-1及图8-2形式。 [ 8 17 25 44 68 77 98 10 115 125 ] low high (a) 初始情形 [ 8 17 25 44 ] 68 44 98 100 115 125 low high mid (b) 经过一次比较后的情形
[8172544]687798100115125 low mid high (c)经过二次比较后的情形(Rmid]key=17) 图8-1查找K=17的示意图(查找成功) [81725446877981001151251 a)初始情形
[8 17 25 44 ] 68 77 98 100 115 125 (c ) 经过二次比较后的情形 (R[mid].key=17) low mid high 图 8-1 查找 K=17 的示意图 (查找成功) [ 8 17 25 44 68 77 98 100 115 125 ] (a) 初始情形 low high
817254468[ 98100115125] mid low high (b)经过一次比较后的情形 8172544687798100[115125] Ow (c)经过二次比较后的情形
8 17 25 44 68 [ 77 98 100 115 125 ] (b) 经过一次比较后的情形 mid low high 8 17 25 44 68 77 98 100 [ 115 125 ] (c) 经过二次比较后的情形 mid low high
8172544687798100115[125] id low high (d)经过三次比较后的情形 1725447798100115125 high low mid (e)经过四次比较后的情形(high<low) 图8-2查找K=120的示意图(查找不成功)
8 17 25 44 68 77 98 100 115 [ 125 ] (d) 经过三次比较后的情形 mid low high 17 25 44 77 98 100 115 125 high low mid (e) 经过四次比较后的情形(high<low) 图 8-2 查找 K=120 的示意图 (查找不成功)