c语言_二分查找（折半查找）

ゝ一纸荒年。 2023-05-22 13:25 79阅读 0赞

A:你的新鞋子好炫酷，多少钱买的呀？  
B:价格在100~300之间，你猜一下咯，每次我只告诉你猜大了还是猜小了，直到你猜对为止，看看你能不能很快猜出来。  
A: ……

小伙伴在生活中有没有和好朋友玩过类似的游戏呢，不知道接下来你会选择何种方式去猜呢？  
  如果从100开始一个一个往后试，就显得稍稍有点无脑了，每次猜测的时候我们可以选择区间中间的数字，这样进行下来，我们每一次的猜测就可以排除一半的当前区间，这样是不是就快了很多呢。类似于这种折半的猜测方式，我们可以把它运用到一个有序数字串当中去，很快判断出我们的目标数字是否在其中。今天我们就用c语言代码来实现一下这个查找方法。

我们以arr\[10\]=\{0,1,2,3,4,5,6,7,8,9\}和目标值key=6为例

**思路图解：**

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

**代码如下：**

#include<stdio.h>
    #include<stdlib.h>
    void BinSearch(int arr[],int size,int key)
    { 
    	int left=0; //左边界初始化
    	int right=size-1; //右边界初始化
    	int mid;  //中间值下标
    	while(left<=right)
    	{ 
    		mid=(left+right)/2; //每次循环先计算当前区间的中间值下标
    		
    		if(arr[mid]<key)    //中间值小于key值的时候，说明key值在当前区间右边
    		{ 
    			left=mid+1;     //我们把区间左边界更新移动到中间下标的下一个位置
    		}	  				//因为中间下标已经小于key值了，我们就没必要再加上它
    		
    		if(arr[mid]>key)	//中间值大于key值的时候，说明key值在当前区间左边
    		{ 
    			right=mid-1;	//我们把区间右边界更新移动到中间下标的前一个位置
    		}					//因为中间下标已经大于key值了，把右边界放到mid-1位置就行
    		
    		if(arr[mid]==key)
    		{ 
    			printf("找到了，下标为%d\n",mid);
    			break;
    		}
     	}
     	//要是没找见，循环结束的时候，left,right,mid在同一个位置
     	//结束位置不等于key,我们就显示提示信息
     	if(arr[mid]!=key)
     	{ 
     		printf("目标数没在其中!\n");
    	}	
    }
    int main()
    { 
    	int arr[10]={ 0,1,2,3,4,5,6,7,8,9}; //数组可以自己scanf
    	int len=sizeof(arr)/sizeof(arr[0]); 
    	BinSearch(arr,len,6); //这里的目标数也可以自己scanf
        return 0;
    }

sizeof是计算变量或者类型所占内存大小的关键字(返回以字节为单位的大小)，sizeof(arr) （数组总共的大小）除以 sizeof(arr\[0\])（数组中一个元素的大小）就等于数组的元素个数。  
PS:二分查找的前提是数字序列必须有序哦！

越努力，越幸福！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70_pic_center]: /images/20230521/fa1480b66ad34cecae5081e03c5aecf5.png