每比较一次,搜索区间缩小一半。如果搜索区间已 缩小到一个对象,仍未找到想要搜索的对象,则搜索 失败 例 有一组有序的线性表如下 (10,14,20,32,45,50,68,90,100,120) 下面分析在其中二分检索关键字20的过程。 下标 01 3 4 5678 1014203245506890100120 ↑个个 lo=2 mid=2 high=3 第3次比较:20=20,检索成功,返回位置2
每比较一次，搜索区间缩小一半。如果搜索区间已 缩小到一个对象，仍未找到想要搜索的对象，则搜索 失败。 有一组有序的线性表如下： （10，14，20，32，45，50，68，90，100，120） 例 下面分析在其中二分检索关键字20的过程
下面分析二分检索关键字95的过程 下标 01 2 3 4 56 789 1014203245506890100120 ↑个 high=7 low=8 此时,high<,即查找区间为空,说明检索失败,返回检索失败信息
下面分析二分检索关键字95的过程:
下面给出二分检索法的非递归与递归实现算法,算法 中使用 eqlist. h中定义的顺序查找表。 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 /*二分查找算法文件名: b search.c* /函数名: binsearch10、 binsearch2 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 二分查找的非递归实现--*/ int binsearch 1(seqlist l, datatype key i int low=0, high=l. len-1, mid while(low<=high) i mid=(low+high)/2
下面给出二分检索法的非递归与递归实现算法，算法 中使用seqlist.h中定义的顺序查找表。 /****************************************************/ /* 二分查找算法 文件名：b_search.c */ /* 函数名：binsearch1()、binsearch2() */ /****************************************************/ /*--------二分查找的非递归实现------*/ int binsearch1(seqlist l,datatype key) { int low=0,high=l.len-1,mid; while (low<=high) { mid=(low+high)/2; /*二分*/
if(. datamid]==key) return mid;/检索成功返回* if(ldata[mid]key) high=mid-1;/*继续在前半部分进行二分检索* else low=md+1;/继续在后半部分进行二分检索* return-1;/当ow>hgh时表示查找区间为空,检索失败*
if (l.data[mid]==key) return mid; /*检索成功返回*/ if (l.data[mid]>key) high=mid-1; /*继续在前半部分进行二分检索*/ else low=mid+1; /*继续在后半部分进行二分检索*/ } return -1; /* 当low>high时表示查找区间为空，检索失败*/ }
二分查找的递归实现 int binsearch2 (seqlist I, datatype key, int low, int high) i int mid, k if (lowshigh) return -1 /*检索不成功的出口条件* else i mid=(low+high)/2 /二分 if( L data[mid]=key) return mid;/检索成功返回* if (L data[mid]key) return binsearch (, key, low, mid-1) /递归地 在前半部分检索* else return binsearch2( key, mid+1,high;/递归地 在后半部分检索*
/*--------二分查找的递归实现------*/ int binsearch2(seqlist l,datatype key,int low,int high) { int mid,k; if (low>high) return -1; /*检索不成功的出口条件*/ else { mid=(low+high)/2; /*二分*/ if (l.data[mid]==key) return mid; /*检索成功返回*/ if (l.data[mid]>key) return /*递归地 在前半部分检索*/ else return /*递归地 在后半部分检索*/ } } binsearch2(l,key,low,mid-1); binsearch2(l,key,mid+1,high);