二分查找（c语言）

二分法

二分法是指对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法。

二分查找
二分查找的效率很高，可以查询很大的数据量，但他的前提是数据需要提前排好序。简单易懂的道理，给出数列1，2，3，4，5，6，7，要从中查出3，我们可以先找到中位数4>3,所以应该在左边查询，我们可以继续在1 2 3中查询，然后找到中位数2<3,所以应该在右边查询，这样就找到3=3；
下面回顾一下高中用二分法求方程近似值的经典例题:利用计算器，求方程 x^2-2x-1=0 的一个近似解（精确到0.1）
先画出大致的图形

设f(x)=x^2-2x-1
f(2)=-1<0,f(3)=2>0；所以一个解在x=（2，3）之间，继续取2和3的中点x=2.5,得f(2.5)=0.25>0,所以解在（2，2.5）之间。
同理不停求解可以得出x=2.4,同理可以求出另外一个解

**给你数列1，2，3，4，5，6，7 你可以一眼看出来，那如果是给你一千万个数呢？这时候需要用到电脑。那么如何用c语言实现二分查找呢?**

/*所谓的二分查找法，其实是一种有序的查找方法，也称折半查找（Binary Search），如果是无序
的则要先进行排序操作。基本思想是：目标值通过与中间元素比较，可分为三种情况： 
第一种情况：目标值与中间元素相等，查找结束； 
第二种情况：目标值比中间元素大，则把后半部分的中间元素与目标值比较； 
第二种情况：目标值比中间元素小，则把前半部分的中间元素与目标值比较； 
这三步一直循环，直到查找结束。*/
#include <stdio.h>
int Bin_Search(int *num,int cnt,int target)
{
    int first = 0,last = cnt-1,mid;
    int counter = 0;
    while(first <= last)
    {
        counter ++;
        mid = (first + last) / 2;//确定中间元素   
        if(num[mid] > target)
        {
            last = mid-1; //mid已经交换过了,last往前移一位
        }
        else if(num[mid] < target)
        {
            first = mid+1;//mid已经交换过了,first往后移一位
        }   
        else //判断是否相等
        {
            printf("查找次数:%d\n",counter);
            return 1;
        }
    }
    printf("查找次数:%d\n",counter);
    return 0;
}

int main(void)
{
    int flag = 0,target;
    int num[10] = {1,2,3,4,5,6,7,8,10};
    while(1)
    {
        printf("请输入您要查找的数字:\n");
        scanf("%d",&target);
        flag = Bin_Search(num,10,target);
        if(flag) printf("已经找到该数字!!\n");
        else printf("无该数字!!\n");    
    }
    return 0;
}