C语言版二分查找法分析

痛定思痛。 2022-05-29 05:38 139阅读 0赞

二分查找法：也称折半查找，它是一种效率较高的查找方法。但是查询的要求为：**线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。**

大致思路：首先，假设表中元素是按升序排列，将表中间位置记录的[关键字][Link 1]与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置[记录][Link 2]将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的[记录][Link 2]，使查找成功，或直到子表不存在为止，此时查找不成功。

时间复杂度：O(h)=O(log2n)

代码实现过程如下：

方法一：非递归实现

#include<stdio.h>
    int HalfSearch(int a[],int low,int hight,int key)
    {
    	int mid;
    	while(low<=hight)
    	{
    		mid=(low+hight)/2;
    		if(a[mid]==key) return mid;
    		else if(a[mid]>key){
    			hight=mid-1;//大于查找关键字，查找前一字表
    		}
    		else{
    			low=mid+1;//小于查找关键字，查找后一字表
    		}
    		}
    		return -1;	
     } 
    int main(void){
     	int h;
     	int a[8]={2,3,4,5,6,7,8,9};
     	h=HalfSearch(a,0,7,2);//主调接收被调函数返回值
     	if(h>=0){
     		printf("该下标为：%d",h);
    	 }else{
    	 	printf("该数不存在该数组里！！！");
    	 } 
     }

方法二：递归实现

#include<stdio.h>
    int HalfSearch(int a[],int low,int hight,int key)
    {
    	int mid;
    	if(low<=hight)
    	{
    		mid=(low+hight)/2;
    		if(a[mid]==key) return mid;
    		else if(a[mid]>key) return HalfSearch(a,low,mid-1,key);//如果中间值大于关键字，中间值-1作为hight继续传给被调进入前一字表
    		else return HalfSearch(a,mid+1,hight,key); //如果中间值小于关键字，中间值+1作为low继续传给被调进入后一字表
    
    }else return -1; } int main(void){ int h; int a[8]={2,3,4,5,6,7,8,9}; h=HalfSearch(a,0,7,2); if(h>=0){ printf("该下标为：%d",h); }else{ printf("该数不存在该数组里！！！"); } }
     
     
    
    
    相关例题应用：
     
     设一个数据序列，查找一个连续子序列，使其和值最大，例如数组a[10]={3,2,-5,8,-4,7,9,-10,1}
     大致思路：设置一层循环，遍历所有起始值，再设置一层循环遍历该起始值下的所有子序列的终点，再设置一层循环遍历起点和终点进行每一次的加和运算，与设置的最大值进行比较，如果大于，则重新给max赋值，找到最大和后，输出该下标和最大值。
     代码实现：
     #include<stdio.h>
    int max,mi,mj;
    void MaxSum(int a[],int n){
    	int i,j,k,sum;
    	for(i=0;i<n;i++){//遍历起点
    		for(j=i;j<n;j++){//遍历终点
    			sum=0;
    			for(k=i;k<j+1;k++){//遍历起点到终点之间的序列
    				sum+=a[k];
    				if(sum>max){
    					mi=i;
    					mj=j;
    					max=sum;
    				}
    			}
    		}
    	}
    } 
    int main(void){
    	int a[10]={3,2,-5,8,-4,7,9,-10,1};
    	max=a[0];//将初始最大值设为数组第一个元素，防止引入外来数字引起代码污染
    	mi=mj=0;
    	MaxSum(a,10);
    	printf("子序列下标%d-%d和最大，最大为：%d",mi,mj,max);
    }

[Link 1]: https://baike.baidu.com/item/%E5%85%B3%E9%94%AE%E5%AD%97
[Link 2]: https://baike.baidu.com/item/%E8%AE%B0%E5%BD%95/1837758