C++
描述在一个非降序列中，查找与给定值最接近的元素。
输入
第一行包含一个整数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
C++ 可以使用二分查找的方法来解决这个问题。首先，我们需要定义一个函数来查找与给定值最接近的元素：
int findClosestElement(int arr[], int n, int target) {
int left = 0; // 左边界
int right = n - 1; // 右边界
// 当左边界小于右边界时，重复查找
while (left < right) {
int mid = left + (right - left) / 2; // 中间元素索引
// 如果中间元素等于目标值，则直接返回
if (arr == target) {
return mid;
}
// 如果中间元素大于目标值，则将右边界移动到中间元素的左边
if (arr > target) {
right = mid;
}
// 如果中间元素小于目标值，则将左边界移动到中间元素的右边
else {
left = mid + 1;
}
}
// 当循环结束时，左边界即为最接近目标值的元素索引
return left;
}
然后，我们可以读入输入数据并调用该函数进行查找：
#include <iostream>
using namespace std;
int main() {
int n; // 序列长度
cin >> n;
int arr; // 序列数组
// 读入序列数据
for (int i = 0; i < n; i++) {
cin >> arr;
}
int target; // 目标值
cin >> target;
// 查找最接近目标值的元素索引
int closestIndex = findClosestElement(arr, n, target);
cout << "最接近目标值的元素为：" << arr << endl;
return 0;
}
这样，我们就可以通过输入一个非降序列和一个目标值，找到与目标值最接近的元素。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。 用二分查找 黎子卿 发表于 2023-11-29 21:58
用二分查找
好的，我们可以使用二分查找算法来实现。下面是用二分查找来查找与给定值最接近的元素的完整代码：
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 二分查找函数
int binarySearch(const vector<int>& arr, int target) {
int left = 0; // 左边界
int right = arr.size() - 1; // 右边界
while (left <= right) {
int mid = left + (right - left) / 2; // 中间元素索引
// 如果中间元素等于目标值，则直接返回
if (arr == target) {
return mid;
}
// 如果中间元素大于目标值，则将右边界移动到中间元素的左边
if (arr > target) {
right = mid - 1;
}
// 如果中间元素小于目标值，则将左边界移动到中间元素的右边
else {
left = mid + 1;
}
}
// 当循环结束时，左边界即为最接近目标值的元素索引
return left;
}
// 查找与给定值最接近的元素
int findClosestElement(const vector<int>& arr, int target) {
// 使用二分查找找到与目标值最接近的元素索引
int index = binarySearch(arr, target);
// 检查最接近元素的左边元素和右边元素，返回距离目标值最接近的元素
if (index == 0) {
return arr;
}
else if (index == arr.size()) {
return arr;
}
else {
if (abs(arr - target) < abs(arr - target)) {
return arr;
}
else {
return arr;
}
}
}
int main() {
int n;// 序列长度
cin >> n;
vector<int> arr(n); // 序列数组
// 读入序列数据
for (int i = 0; i < n; i++) {
cin >> arr;
}
int target; // 目标值
cin >> target;
int closestElement = findClosestElement(arr, target); // 查找最接近目标值的元素
cout << closestElement << endl;
return 0;
}
这段代码首先定义了一个二分查找函数`binarySearch`，然后定义了一个`findClosestElement`函数用于查找与给定值最接近的元素。在主函数中，我们读入序列长度、序列数据和目标值，并调用`findClosestElement`函数来查找最接近目标值的元素，并将结果输出。
请注意，这里假设输入的序列是非降序排列的。如果需要处理其他类型的序列，请根据实际情况进行相应的调整。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。 FishC_GPT 发表于 2023-11-29 21:58
好的，我们可以使用二分查找算法来实现。下面是用二分查找来查找与给定值最接近的元素的完整代码：
为什么当循环结束时，左边界即为最接近目标值的元素索引 黎子卿 发表于 2023-11-29 22:03
为什么当循环结束时，左边界即为最接近目标值的元素索 ...
在二分查找算法中，我们通过不断更新左边界和右边界来缩小查找范围，直到左边界等于右边界。这时候，我们已经找到了目标值的插入位置，即左边界所在的位置。
当循环结束时，如果目标值存在于数组中，那么左边界所在的位置就是该元素的索引。如果目标值不存在于数组中，那么左边界所在的位置就是离目标值最接近的元素的插入位置。
我们之所以选择左边界作为结果返回，是因为题目要求查找与给定值最接近的元素。在非降序列中，左边界一定比右边界更接近目标值，所以选择左边界即可。
需要注意的是，当数组中有多个与目标值最接近的元素时，返回左边界可能并不是唯一的正确答案。这种情况下，你可以根据题目要求进一步处理，如返回多个最接近的元素。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
页:
[1]