从上述查找思想可知，每进行一次关键字比较，区间数目增加一倍，故称为二分（区间一分为二），而区间长度缩小一半，故也称为折半（查找的范围缩小一半）。2.二分查找算法实现intbinsearch(nodeR[n+1],，elemtype k)1intlow=1, mid, high=n;while(low<=high)/取区间中点mid=(low +high)/2:if/查找成功mid;(R[mid].key= =k)returnelse if (R[mid].key>k)在左子区间中查找high=mid-1;/在右子区间中查找elselow=mid+1;//查找失败return O;}
从上述查找思想可知，每进行一次关键字比较，区间数 目增加一倍，故称为二分（区间一分为二），而区间长 度缩小一半，故也称为折半（查找的范围缩小一半）。 2．二分查找算法实现 int binsearch (node R[n+1], elemtype k) { int low=1, mid, high=n; while (low<=high) { 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.77.98.100.115.125，将查找K=17和K=120的情况描述为图8-1及图8-2形式。10817254477981151256811highlow(a)初始情形17254498100115125r 844681midlowhigh经过一次比较后的情形(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) 经过一次比较后的情形
18172544687798100115125个lowmidhigh(c）经过二次比较后的情形(R[midj.key=17)图8-1查找K=17的示意图（查找成功）25446898177710011512518lowhigh(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
8172544698100115125]6877一lowmidhigh(b)经过一次比较后的情形8172544687798100115125一1midlowhigh(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
100115［125]8172544687798midlow high经过三次比较后的情形(d)1001151251725447798个个highlow mid经过四次比较后的情形（high<low）(e)图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 的示意图 (查找不成功)