c语言_二分查找（折半查找）-蒲公英云

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

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

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

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

思路图解：

在这里插入图片描述

代码如下：

#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;
}