NOI 1.11.1 查找最接近的元素

题目：查找最接近的元素

描述

在一个非降序列中，查找与给定值最接近的元素。

输入

第一行包含一个整数n，为非降序列长度。1 <= n <= 100000。
第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。
接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。

输出

m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

样例输入

3
2 5 8
2
10
5

样例输出

8
5

限制条件

总时间限制: 1000ms 内存限制: 65536kB

思路：

在基础二分的思想下，我们很容易想到对数组里的数进行二分查找。

如果要查找的数在数组中存在，那么定义的函数直接返回该值。如果不存在，那么二分查找的左端点和右端点会停留在目标数的左右两端。

此时，只要将左端点和右端点所对应的数组中的值与目标数进行比较，差值小的即最接近目标数。要注意的是：计算差值需要加绝对值

但是只想到这里明显是不够的，此题存在陷阱

因为我们进行二分查找的前提是要对目标数组进行排序，这里我们以升序为例：

​ 如果目标数小于该数组中的最小值那么右端点将会在数组中越界，导致奇奇怪怪的错误。

​ 如果目标数大于该数组中的最小值那么左端点将会在数组中越界，也会导致奇奇怪怪的错误。

因此，我们要进行特判：

​ 如果目标数小于该数组中的最小值，那么最后直接输出数组中最小的数，反之亦然。

题解：

#include<iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define int long long//将long long 变为int此题数据有点大
using namespace std;
int binaryseach(int a[], int size, int p)//函数作用：在长度为size+1（因为我习惯下标从1开始）的a数组里查找最接近p的数
{
    int l = 1, r = size;//设置左右端点
    while (l <= r)//二分模板
    {
        int mid = l + (r - l) / 2;//若用（l+r）/2可能在某些题中会导致数据溢出
        if (p == a[mid])
        	return p;
        else if (p < a[mid])
        	 r = mid-1;
        

        else if (p > a[mid])
        	 l = mid+1;
    }
    if (p < a[1])//特判
        return a[l];
    else if (p > a[size])
        return a[r];
    else//比较最接近p的数
    {
        int x1 = abs(a[l] - p);
        int x2 = abs(a[r] - p);
        if (x1 < x2)
            return a[l];
        else
            return a[r];
    }

}
signed main()//因为上面将long long 变为了 int 而main函数类型不能为 long long ,故改为signed
{
    int n;
    cin >> n;
    int arr[100010];
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    sort(arr + 1, arr + 1 + n);//排序
    int num;
    cin >> num;
    while (num--)
    {
        int x;
        cin >> x;
        cout << binaryseach(arr, n, x) << endl;
    }
    

    return 0;

}