29-折半查找法的使用

布满荆棘的人生 2022-12-22 04:56 137阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

#include <stdio.h>
    
    //利用顺序查找,在无序的数组arr中,查找key,找到返回下标,失败返回-1
    int Search(int *arr,int len,int key)
    {
        
    	for(int i=0;i<len;i++)
    	{
        
    		if(arr[i] == key)
    		{
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    //利用折半查找,在有序(升序)的数组arr中,查找key,找到返回下标,失败返回-1
    int BinSearch1(int *arr,int len,int key)//错误，存在bug，存在low=high=key 
    {
        
    	int low = 0;//起始下标
    	int high = len-1;//结尾下标
    	int mid;//中间位置下标
    
    	while(low < high)
    	{
        
    		mid = (low+high)/2;
    		if(arr[mid] == key)
    		{
        
    			return mid;
    		}
    		else if(arr[mid] < key)//在右边
    		{
        
    			low = mid;//可能出现死循环 
    		}
    		else
    		{
        
    			high = mid;//可能出现死循环
    		}
    	}
    	return -1;
    }//错误运行，输出结果为；-1.-1.0.1.2.3.4.5.6.7.8.9.10 
    
    int BinSearch(int *arr,int len,int key)//正确的写法 
    {
        
    	int low = 0;//起始下标
    	int high = len-1;//结尾下标
    	int mid;//中间位置下标
    
    	while(low <=high)
    	{
        
    		mid = (low+high)/2;
    		if(arr[mid] == key)
    		{
        
    			return mid;
    		}
    		else if(arr[mid] < key)//在右边
    		{
        
    			low = mid+1;
    		}
    		else
    		{
        
    			high = mid-1;
    		}
    	}
    	return -1; 
    } 
    
    int main()
    {
        
    	int arr[] = {
        1,2,3,4,5,6,7,8,9,10,11,12};
    	/*for(int i=-1;i<15;i++)
    	{
    		printf("%d\n",BinSearch1(arr,sizeof(arr)/sizeof(arr[0]),i));
    	}*/
    	for(int i=-1;i<15;i++)
    	{
        
    		printf("%d\n",BinSearch(arr,sizeof(arr)/sizeof(arr[0]),i));
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/aa76bb8a74ed4f6f8a9f83d0624296aa.png