在这篇文章中，我们被给定了一个问题，给定了一个数组，并且有两种类型的查询需要回答。
类型 0 – 我们需要计算大于等于 x（给定值）的元素的数量。类型 1 – 我们需要计算严格大于 x（给定值）的元素的数量。
所以这里有一个简单的例子 –
Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3 Query 1: 0 50 Query 2: 1 40 Query 3: 0 30Output : 0 1 3Explanation: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个查询，并找到满足条件的数字。
立即学习“C++免费学习笔记（深入）”；
示例
#include using namespace std;void query(int *arr, int n, int type, int val) { int count = 0; // answer if(!type) { // when type 0 query is asked for(int i = 0; i = val) count++; } } else { // when type 1 query is asked for(int i = 0; i val) count++; } } cout 输出
013
登录后复制
在上述方法中，我们只是遍历数组并计算查询的答案；这种方法对于给定的示例是有效的，但如果遇到更高的约束条件，这种方法将失败，因为程序的总时间复杂度是O(N*Q)，其中N是数组的大小，Q是查询的数量，所以现在我们将优化这种方法，使其适用于更高的约束条件。
高效的方法
在这种方法中，我们将使用二分查找来找到给定值的上界和下界。我们首先使用二分查找对数组进行排序，然后根据需要应用我们的下界和上界函数。
示例
#include using namespace std;void lowerbound(int *arr, int n, int val) { int l = -1, r = n; while(r - l > 1) { // binary searching the answer int mid = (l+r)/2; if(arr[mid] >= val) r = mid; else l = mid; } if(r == n) // if r is unmoved then it means there is no element that satisfy the condition cout 1) { // binary searching the answer int mid = (l+r)/2; if(arr[mid] > val) r = mid; else l = mid; } if(r == n)// if r is unmoved then it means there is no element that satisfy the condition cout 输出
012
登录后复制
上面的代码使用了二分搜索，大大减少了时间复杂度。因此，我们的最终复杂度为O(NlogN)，其中N是数组的大小。
上述代码的解释
在这种方法中，我们将使用二分搜索来找到给定值的上界和下界。现在对于二分搜索，我们首先对数组进行排序，因为它只适用于排序后的数组。我们创建一个lower bound和一个upper bound函数，帮助我们找到满足类型0和类型1条件的第一个数字，现在我们已经对数组进行了排序。我们找到了满足条件的第一个数字，所以在这个元素之后的元素也满足条件，因此我们打印出该元素与N（数组的大小）的索引之差。
结论
在本文中，我们解决了使用二分搜索解决大于和不小于的查询问题。我们还学习了这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言（如C、Java、Python和其他语言）编写相同的程序。希望您觉得这篇文章有帮助。
以上就是使用C++编写大于和不小于的查询的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583333.html
