在本文中，我们给出了一个问题，给出了一个数组，我们需要回答两种类型的查询。
类型 0 - 我们必须计算大于或等于 的元素的数量x(given value)。
类型 1 - 我们必须计算严格大于 的元素的数量x(given value)。
所以这是一个简单的例子 -
Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
Query 1: 0 50
Query 2: 1 40
Query 3: 0 30
Output :
0
1
3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30.我们可以使用两种不同的方法来找到解决方案。首先我们将使用蛮力解决方案，然后检查它是否适用于更高的约束。如果没有，那么我们继续优化我们的解决方案。
在这种方法中，我们将遍历所有 q 查询的数组并找到满足给定条件的数字。
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // 回答
if(!type) { // 当询问类型 0 查询时
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // 当询问类型 1 查询时
for(int i = 0; i < n; i++) {
if(arr[i] > val)
count++;
}
}
cout << count << "\n";
}
int main() {
int ARR[] = { 10, 15, 30, 40, 45 };
int n = sizeof(ARR)/sizeof(ARR[0]); // 我们数组的大小
query(ARR, n, 0, 50); // 查询 1
query(ARR, n, 1, 40); // 查询 2
query(ARR, n, 0, 30); // 查询 3
return 0;
}输出结果0 1 3
在上述方法中，我们只是简单地遍历数组并计算查询的答案；这种方法适用于给定的示例，但如果我们遇到更高的约束，这种方法将失败，因为程序的整体时间复杂度为 O(N*Q)，其中 N 是数组的大小，Q 是查询的数量所以现在我们将优化这种方法，使其也适用于更高的约束。
在这种方法中，我们将使用二分搜索来查找给定值的上限和下限。我们首先使用二分搜索对数组进行排序，然后相应地应用我们的下限和上限函数。
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // 二分法寻找答案
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // 如果 r 不动则表示没有满足条件的元素
cout << "0\n";
else
cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // 二分法寻找答案
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n)// 如果 r 不动则表示没有满足条件的元素
cout << "0\n";
else
cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // 如果 type == 0 我们调用下界函数
lowerbound(arr, n, val);
else // 如果 type == 1 我们调用上界函数
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // 我们数组的大小
sort(arr, arr+n); // 对数组进行排序
query(arr, n, 0, 5); // 查询 1
query(arr, n, 1, 3); // 查询 2
query(arr, n, 0, 3); // 查询 3
return 0;
}输出结果0 1 2
上面的代码适用于二进制搜索，大大降低了我们的时间复杂度。因此，我们的最终复杂度变为O(NlogN)，其中 N 是数组的大小。
在这种方法中，我们将使用二分搜索来查找给定值的上限和下限。现在对于二分搜索，我们首先对数组进行排序，因为它仅适用于已排序的数组。现在我们已经对数组进行了排序，我们创建了下限和上限函数，帮助我们找到分别满足类型 0 和类型 1 条件的第一个数字。我们找到了第一个帮助条件的数字，所以这个元素后面的元素也遵循这个条件，所以我们打印这个元素的索引与 的差值N(the size of our array)。
在本文中，我们解决了一个问题，以解决大于和不小于使用二分搜索的查询。我们还学习了针对这个问题的 C++ 程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。我们希望这篇文章对您有所帮助。