二分法查找（初学者）

适用情况：在一批有序数据中查找某数。

基本思想：

1 确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ.

2 求区间(a,b)的中点c.

3 计算f(c).

(1) 若f(c)=0,则c就是函数的零点;

(2) 若f(a)·f(c)<0,则令b=c;

(3) 若f(c)·f(b)<0,则令a=c.

(4) 判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4.

例：假设数组a中的数据是按由小到大的顺序排列的：-12，0，6，16，23，56，80，100，110，115，从键盘上输入一个数，判定该数是否在该数组中，若在，输出所在序号。

（假设输入的数为80）第一步：设low、mid和high三个变量，分别指向数列中的起始元素，其初始值为low=0，high=9，mid=4，判断mid指示的数是否为所求。mid指示的数是23，不是要找的80，仍继续查找。

第二步：确定新的查找区间，因为80大于23，所以查找的范围可以缩小为23后面的数，新的查找区间为[56,80,100,110,115]，low，mid，high分别指向新区间的开始，中间和最后一个数。实际上high不变，将low（low=mid+1）指向56，mid（mid=(low+high)/2）指向100，还不是要找的80，仍继续查找。

第三步：上一步中，所找数80比mid指示的100小，可知新的查找区间为[56，80]，low不变，mid与high的值作相应修改。mid指示的数为56，还要继续查找。

第四步：根据上一步的结果，80大于mid指示的数56，可确定新的查找区间为[80]，此时，low与high都指向80，mid亦指向80，即找到了80，到此为止，查找过程完成。

注：若在查找过程中，出现low>high的情况，则说明，序列中没有该数，亦结束过程。

参考程序：

#include <stdafx.h>
#include<stdio.h>

void main()
{
    int a[10]={-12,0,6,16,23,56,80,100,110,115},low,mid,high,found,n;
    low=0;
    high=9;
    mid=4;
    found=0;
    printf("Input a number to be searched:");
    scanf("%d",&n);
    for(;low<=high;mid=(low+high)/2)
    {
        if(n==a[mid])
        {
            found=1;
            break;
        }
        if(n>a[mid])
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    if(found==1)
    {
        printf("The index of %d is %d",n,mid);
    }
    else
    {
        printf("There is not %d",n);
    }
    

}