折半查找法

待我称王封你为后i 2022-03-17 01:06 275阅读 0赞

折半查找法:

1.  首先的条件就是该数组是有序的
2.  再次把数组对半拆
3.  然后将查找的数与数组中间的数作比较
4.  比较后有三种情况:  
    (1) 等于中间的数  
    (2)比中间的数要小  
    (3)比中间的数要大

下面通过代码举例

#include <stdio.h>
    #define N 5
    int i;
    int main(){
    	void input(int []);//输入N个数
    	void sort(int []);//给数组排序
    	void output(int []);//输出N个数
    	void search(int,int []);//从主函数中输入一个数去到数组中查找
    	int num[N];
    	input(num);//输入9 7 5 3 1
    	sort(num);
    	output(num);
    	search(5,num);//查找5
    	search(0,num);//查找0
    	search(6,num);//查找6
    	return 0;
    }
    
    void input(int num[]){
    	for(i=0;i<N;i++)
    		scanf("%d",&num[i]);
    }
    
    void sort(int num[]){
    	int j,k,t;
    	//选择排序法
    	for(i=0;i<N-1;i++){
    		k=i;
    		for(j=i+1;j<N;j++)
    			if(num[k]>num[j])//从小到大
    				k=j;
    		if(k!=i){
    			t=num[i];
    			num[i]=num[k];
    			num[k]=t;
    		}
    	}	
    }
    
    void output(int num[]){
    	for(i=0;i<N;i++)
    		printf("%-2.0d",num[i]);
    	printf("\n");
    }
    
    void search(int n,int num[]){
    	int start=0,mind,end=N-1,sign=0,local;//start:头元素位置,mind:中间元素位置,end:最后一个元素位置,local:记录要找的数在数组中的下标,sign:是否在数组中找到
    	if(n<num[start]||n>num[end])
    		local=-1;//不在数组范围内
    	while(!sign&&start<=end){
    		mind=(start+end)/2;//得到中间的元素下标
    		if(n==num[mind]){
    			local=mind;
    			printf("%d在数组中的第%d个位置\n",n,local+1);//local+1是因为数组下标从0开始的
    			sign=1;//已找到
    		}
    		else if(n<num[mind])//位置在中间元素的左边
    			end=mind-1;//缩小范围
    		else//在中间元素的右边
    			start=mind+1;
    	}
    	if(local==-1||!sign)//不在范围内或者数组中没有该数
    		printf("找不到%d!\n",n);
    }

测试结果如下:  
![在这里插入图片描述][20190221200944169.png]

[20190221200944169.png]: /images/20220317/c6b94a44f66f46bca59f2dca185ab490.png