二分查找与二分答案（1）

我们在写程序的时候，经常会遇到这样一类问题：在一个数组中查找一个数是不是存在。比如在下图的数组中，查找 8 是不是存在：
如果不要求效率，我们最一般的查找方法就是顺序查找，依次查看 a [0], a [1], …, a [n-1]，检查是不是等于 8。这样对于长度为 n 的数组，平均查找长度是 n/2

如果数组是有序的，比如是递增的，就像上图 [1, 2, 3, 4, 5, 7, 8, 10, 11, 13] 一样的话。我们就有效率更高的查找算法，叫做二分查找。例如还是在上面数组中查找 8

1. 我们直接找位于中间的数 a [4]，发现 a [4]=5，比 8 要小，所以如果 8 在这个数组里，肯定在 a [5]~a [9] 之中
2. 我们找 a [5]-a [9] 这个范围里位于中间的数 a [7], 发现 a [7]=10，比我们要找的数大，所以如果 8 在这个数组里，肯定在 a [5]-a [6] 之中
3. 我们找 a [5]~a [6] 这个范围里位于中间的数 a [5]，发现 a [5]=7，比我们要找的 8 小。所以我们知道如果 8 在数组里，那它肯定是 a [6] 这个数
4. 我们查看 a [6] 的值，发现 a [6]=8，于是我们找到了 8 的位置。假如我们这时发现 a [6] 不是 8，则说明 8 没有在这个数组里

二分查找又叫 “折半查找”。因为我们每进行一步，也就是查看一个元素的数值，都会使得后面需要检查的范围缩小一半。二分查找的时间复杂度是 $O (\log N)$ 的，换句话说，在长度为 N 的有序数组中查找一个数，查看元素的次数最多是 $\log N+1$ 次。当 N 很大时，二分查找的速度比顺序查找快非常多倍

#include<iostream>
using namespace std;
int n,x,a[1000000];
int binary_search(int a[],int n,int x)
{
    int l = 0;
    int r = n - 1;
    int ans = -1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if(a[m] == x)
        {
            ans = m;
            break;
        }
        if(a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return ans;
} 
int main()
{
    cin >> n >> x;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    int ans = binary_search(a,n,x);
    cout << ans;
    return 0;
}