坠菜的我熬过期末又回来了！！！二分查找。。。

五校联考真是一个奇怪的东西，对大家都有害，但是大家还都屁颠屁颠的去做。。。（就不提八中出的自杀式物理卷了，玉石俱焚）

二分查找是一个好东西，至于好在哪，我也不知道，也许它是后面某个算法的基础。不管怎样，学了再说。

先看一下代码（嫌麻烦，没把函数单拿出来，见谅）

题目：

描述

    在一个非降序列中，查找与给定值最接近的元素。
输入
    第一行包含一个整数n，为非降序列长度。1 <= n <= 100000。
    第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
    第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。
    接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。
输出
    m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

个人题解：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    long long int a[100000],b[10000];
    long int n,m,low=0,middle,high;
    bool flag=true;
    cin>>n;
    high=n-1;
    for(long i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cin>>m;
    for(long i=0;i<m;i++)
    {
        cin>>b[i];
    }
    sort(a,a+n);
    for(long j=0;j<m;j++){
        while(low<=high){
            middle=(low+high)/2;
            if(a[middle]==b[j]){
                cout<<a[middle]<<endl;
                flag=false;
                break;
            }
            if(a[middle]<b[j])
            low=middle+1;
            if(a[middle]>b[j])
            high=middle-1;
            middle=(low+high)/2;
        }
        if(flag==true){
            int l1=a[middle]-a[low];
            int l2=a[high]-a[middle];
            if(l1>=l2)
            cout<<a[low]<<endl;
            else
            cout<<a[high]<<endl;
        }
        flag=true; 
        high=n-1;
        low=0;
    }
    return 0;
}

有趣吧！也许不是很完善，欢迎指正！

下面是个人一些不成熟的见解：

首先把目标数组排序（直接sort），再找3个指针（不用指针也行，我就用的普通变量模拟指针）一个代表范围的开头，一个代表范围的结尾，最后一个表示最中间的一个变量。

前面的其实都是准备过程，下面开始真正的二分（仅解释一组）。首先，判断尾指针是否大于头指针，如果否，就可以直接输出结束了；如果是，就进行定位中间的指针。middle=（low+high）/2。这很好理解吧。

然后判断中间值所代表的值与目标值的大小关系，如果相等，直接输出跳出循环。如果大于该值，则将尾指针变为middle-1，反之则便为头指针为middle+1。为什么要这样呢？因为，假如不-1或+1，程序就会变成一个死循环，永远退不出去。。。

最后判断是否尾大于头，是则继续循环，否则进行判断，判断现在的头和尾那个距离目标值较近，输出距离目标值较近的那一个，over。

还好吧，最后补一句，总算考完了，解放啦！！！