概述

这篇文章所要讲的二分查找，是一种效率很高的查找方法。二分查找可以将查找的时间复杂度降至*O(log2n)*，但是它要求所查找的数列至少是有序数列。在大部分题目中，这个数列会被规定为有序且连续，但在某些题目中，数列不是连续的，而如果无法查找到，则输出固定语句。这些大同小异，但是用二分查找的前提一定是该数列有序。

正文

具体示例

当我们在电话本中查找我们想要的人的电话号码时，我们通常知道想要查找的人的姓名，而电话本中记录的顺序完全按照姓名字母的字典序。我们通常如何查找？

先翻到电话本的一半，判断一半时候的姓名字母是在目标姓名字母的前边还是后边，然后再在目标姓名字母存在的部分继续上述过程，最终可以查到目标电话号码，这就是二分查找的具体应用之一。

原理

二分查找1.jpg

如图所示，在当前数列中查找6是否存在，若存在，输出其其中一个序号。

已知当前数列为非递减数列。首先，确定left为数列最左端，right为数列最右端。即left为1，right为11。设置mid变量，存储数列中点序号。在当前图所示状态下，mid取值为6，即6为该数列当前中点，只需比较所求数与中点所对应的数字。

由于9>6，可知所求数所对应序号只可能在6之前，也就是只可能存在于1到6之间。故用当前mid-1替换当前right。（之所以用mid-1是为了防止出现无限循环的情况）

二分查找2.jpg

此时mid为（1+5）/2即3。将所求数与序号3对应数字对比，5<6，故所求数所对应序号只可能在3后，也就是只可能存在于3到6之间。故用当前mid+1替换当前left。（原因同上）

二分查找3.jpg

此时mid为（4+5）/2即4。将所求数与序号4对应数字对比，发现正好相等。代表该数列中6确实存在，故可以输出目标数字对应的序号。

若left>right，代表给出的数列已经查找完，没有发现目标数字。

注意事项

应用二分查找法的前提一定是有序数列。
二分查找法在应用时应密切注意各变量的限值重叠交叉问题，不然可能会出现死循环。

标准代码

给出我手打的标准代码（默认给出的15个数有序）

#include<stdio.h>
int main()
{
    int l,r,i;
    int goal;
    int mid;
    int pd=0;
    int a[20];
    scanf("%d",&goal);
    for(i=1;i<=15;i++)
    {	
        scanf("%d",&a[i]);
    }
    l=1;
    r=15;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]==goal)
        {
            printf("%d",mid);
            pd=1;
            break;
        }
        else if(a[mid]<goal)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    if(pd==0)
    {
        printf("no answer");
    }
    return 0;
}

通常的，每一个二分查找的题目中应包含两个条件。一个是判断找到的标准，一个是判断无法找到的精度。在我上面的代码中，找到的标准就是目标数字等于了当前判断的数字，代表二分查找已经查找到了。判断精度则是无限接近于0，原因是我判断的标准是当l>r时结束。在某些题目中，精度有明显给出，可以写成r-l<精度的格式。有时，判断精度也可通过固定循环次数代替。

相关题目

先提一句，在openjudge–noi上面有一个系列共十道二分法的题目。

查找最接近的元素–openjudge-noi

http://noi.openjudge.cn/ch0111/01/

二分查找4.1.jpg

基本是道裸二分查找，没啥好说的……

打出了ac代码，emmm我代码风格也不好，各人有各人的作法……

#include<stdio.h>
#include<math.h>
int a[100005]={-1};
int l,r;
int n,m,t;
int i;
int mid,ans,ans1;
int jdz(int cs)
{
    if(cs<0)
    {
        return -cs;
    }
    else
    {
        return cs;
    }
} 
int bj(int a1,int a2,int p)
{
    if(a1==-1)
    {
        a1=-999;
    }
    if(a2==-1)
    {
        a2=-999;
    }
    if(jdz(a1-p)<=jdz(a2-p))
    {
        return a1;
    }
    else
    {
        return a2;
    }
}
int cz(int q)
{	
    l=1;
    r=n;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]<=q)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    mid=(l+r)/2;
    ans1=bj(a[mid],a[mid+1],q);
    a[0]=-1;
    a[n+1]=-1;
    return ans1;
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&t);
        ans=cz(t);
        printf("%d\n",ans);
    }
    return 0;
}