Linux洗C语言基础编程——折半查找法

古城微笑少年丶 2022-07-16 04:12 157阅读 0赞

今天我们写一个选择法排序与折半查找法相结合的程序。主要实现先排序在查找。前面我们已经详细的讲过了选择排序法，现在我们来说下折半查找法

折半查找法的主要思想是 number与mid的比较

mid = （butt+top）/2

如果number大于mid，则top = mid+1；

如果number小于mid，则butt = mid-1；

下面附上我的代码，如有不合理的地方，请指正！

#include <stdio.h>
    #define N 15
    
    void binsearch(int a[N])/*折半查找*/
    {
    	int top;
    	int but;
    	int mid;
    	int flag;
    	int num;
    	int sign;
    	int loca;
    
    	char c;
    
    
    	flag = 1;
    
    	while(flag)
    	{
    		printf("input the number you want to search!");
    		scanf("%d",&num);
    
    		top = 0;
    		sign = 0;
    		but = N - 1;
    
    		if((num < a[0]) && (num >a[N-1]))
    		{
    			loca = -1;
    		}
    
    		while((!sign) && (top <= but))
    		{
    			mid = (top + but)/2;
    
    			if(num == a[mid])
    			{
    				loca = mid;
    				printf("Has found the number %d,its postion is %d\n",num,loca + 1);
    				sign = 1;
    			}
    			else if(num > a[mid])
    			{
    				top = mid +1;
    			}
    			else
    			{
    				but = mid -1;
    			}
    		}
    
    		if(!sign || loca == -1)
    		{
    			printf("Can not find the number!\n");
    		}
    		
    		printf("continue or no [Y/N]:\n");
    		
    		scanf(" %c",&c);
    
    		if(c == 'N' || c == 'n')
    		{
    			flag = 0;
    		}
    
    	}
    
    
    }
    
    void choicearrange(int a[N])/*选择法排序*/
    {
    	int i;
    	int j;
    	int k;
    	int temp;
    
    	for(i = 0; i < N-1; i++)
    	{
    		k = i;
    		for(j = i + 1; j < N; j++)
    		{
    			if(a[k] > a[j])
    			{
    				k = j;
    			}
    		}
    
    		if(k != i)
    		{
    			temp = a[k];
    			a[k] = a[i];
    			a[i] = temp;
    		}
    	}
    }
    
    int main()/*主函数*/
    {
    	int a[N];
    	int i;
    
    	for(i = 0; i < N; i++)
    	{
    		scanf("%d",&a[i]);
    	}
    
    	choicearrange(a);
    	
    	for(i = 0 ;i < N; i++)
    	{
    		printf("%-3d",a[i]);
    	}
    	printf("\n");
    
    	binsearch(a);
    
        return 0;
    }

程序运行结果见下图：

![Center][]

[Center]: /images/20220716/b7aa3f27b4844d3aaf08722321f7cef5.png