博客

最近元素 (Standard IO)

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目：在一个

非降序列

中，查找与给定值最接近的元素。

输入

第一行包含一个整数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

数据范围限制

1 <= n <= 100000。

#include <iostream>
#include <cmath>
using namespace std;

const int N = 1000000;
int a[N];

int BinarySearch(int low, int high, int x);  // 函数声明 

int main()
{
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	int m;
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		int result = BinarySearch(0,  n - 1, x);   // 函数调用 
		cout << a[result] << endl; 
	}
	return 0;
}

// 二分查找 
int BinarySearch(int low, int high, int x)   // 函数定义 
{
	int mid;
	while (low < high)
	{
		mid = (low + high) / 2;    // 中间值 
		
		if(x == a[mid])
			return mid;
		else if (x > a[mid])
			low = mid;
		else
			high = mid;
		
		//  若找不到，mid会在中间，这时判断前面的数和后面的数差值哪个大哪个小
		if (low + 1 == high)
		{
			if (abs(x - a[low]) > abs(x - a[high]))
				return high;
			else
				return low;	
		}
	}
}