【阅读部分】 在一个有序的数据序列里，如果要查找一个数，普通的办法是从头到尾扫描一遍，但是这样的时间复杂度是O（n）级别。如果有m次查询，那么时间复杂度就达到了O(mn）级别，数据大就超时了。

下面介绍一种O(lg(n))的查找方法，那就是二分查找。

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

步骤：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二分查找，只要查找log2(n)次，即可找出答案。而log2(1000000）≈20，速度实在是高效得逆天。

折半查找有递归写法和非递归写法。

1、递归写法：

int bin_search(int key[],int low, int high,int k)  //注意：high的值是数组的最后一个单元位置，不是数组元素个数 
//key 源数据数组，假设已从小到大排序 。low：查找区域的前端点；high：查找区域的后端点；k：要查找的值 
{  
    int mid;  
    if(low>high)  //如果数组里没有要查找的数据，返回 -1 
        return -1;  
    else{  
        mid =low+ (high-low) / 2;  //先计算查找区域的中点位置。也有写成：mid = (low+high) / 2;  但如果low和high很大会有溢出int范围的风险 
        if(key[mid]==k)           //如果mid位置的值就是要查找的，就把mid的值返回 
            return mid;  
        if(k>key[mid])            //如果要找的值比mid位置的值大，那么就到后半部分查找 
            return bin_search(key,mid+1,high,k);        /*在序列的后半部分查找*/  
        else  
            return bin_search(key,low,mid-1,k);            /*在序列的前半部分查找*/  
    }  
}

主程序调用：weizhi=bin_search(a,0,n-1,x); //假设a数组已从小到大排序。n是数组数据个数，注意要 -1 。x是要找的数据

2、非递归写法：

int bin_search(int key[],int n,int k)// key 源数据数组，假设已从小到大排序 。n：数组数据个数；k：要查找的值 
    int l=0,r=n-1;  // l:数组起点位置  r：数组终点位置，是数据总个数 -1 
    while(l<=r){
        int mid =l+ (r-l) / 2;  //如果n不大的话也可以写成：mid=(l+r)/2;
        if(key[mid]>k)r=mid-1;  //如果要找的数在前半段，那么修改后端点的值 
        else if(key[mid]<k)l=mid+1;  //如果要找的数在后半段，那么修改前端点的值 
        else return mid;    //如果mid位置的值就是要查找的，就把mid的值返回 
    }
    return -1;  //如果数组里没有要查找的数据，返回 -1 
}

主程序调用：weizhi=bin_search(a,n,x); //假设a数组已从小到大排序。n是数组数据个数 。x是要找的数据

题目描述

给出从小到大排列的n个不同数a[1]~a[n]，试判断元素x是否出现在表中。如果在则输出"yes",否则输出“no”

输入格式

输入有三行。

第一行一个数n。（1 ≤ n ≤ 500000）

第二行有n个数。

第三行为要查找的数。

输出格式

如果在则输出"yes",否则输出“no”

样例

6
1 2 3 4 5 6
3

yes

数据范围