题目描述 请在一个有序不递减的数组中(数组中的值有相等的值),采用二分查找,找到第1个大于或等于元素x的位置,如果不存在,请输出-1。 请注意:本题要求出q个x,每个x在数组找到第1个大于或等于x的元素的位置。 比如有6个数,分别是:1 2 2 2 6 6,那么如果要求3个数:5 8 2,在数组中找到第1个大于或等于他们的位置,答案是:5 -1 2。 输入: 第一行,一个整数n,代表数组元素个数(n <= 105) 第二行,n个整数,用空格隔开,代表数组的n个元素(1<=数组元素的值<=108) 第三行,一个整数q,代表有要查询q个数(q<=105) 第四行,q个整数,用空格隔开,代表查询的数(1<=要找的数<=108) 输出: 按题意输出位置或者-1。 样例输入: 6 1 2 2 2 6 6 3 5 8 2 样例输出 : 5 -1 2 用c++代码编写
时间: 2024-04-12 14:30:10 浏览: 85
对于这个问题,你可以使用二分查找算法来找到第一个大于或等于给定元素x的位置。以下是一个用C++编写的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int x) {
int left = 0;
int right = arr.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= x) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
int result = binarySearch(arr, x);
cout << (result != -1 ? result + 1 : -1) << " ";
}
return 0;
}
```
你可以将输入的样例传递给该程序,并查看输出结果是否符合预期。
阅读全文