在這篇文章中，我們被給定了一個問題，給定了一個數組，並且有兩種類型的查詢需要回答。
所以這裡有一個簡單的範例 -
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; // answer
if(!type) { // when type 0 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // when type 1 query is asked
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]); // size of our array
query(ARR, n, 0, 50); // query 1
query(ARR, n, 1, 40); // query 2
query(ARR, n, 0, 30); // query 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) { // 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 << "0\n";
else
cout << n - r << "\n";
}
void upperbound(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 << "0\n";
else
cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // if type == 0 we call lower bound function
lowerbound(arr, n, val);
else // if type == 1 we call upperbound function
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // size of our array
sort(arr, arr+n); // sorting the array
query(arr, n, 0, 5); // query 1
query(arr, n, 1, 3); // query 2
query(arr, n, 0, 3); // query 3
return 0;
}0 1 2
上面的程式碼使用了二分搜索，大大減少了時間複雜度。因此，我們的最終複雜度為O(NlogN)，其中N為陣列的大小。
在這種方法中，我們將使用二分搜尋來找到給定值的上界和下界。現在對於二分搜索，我們首先對數組進行排序，因為它只適用於排序後的數組。我們建立一個lower bound和一個upper bound函數，幫助我們找到滿足類型0和類型1條件的第一個數字，現在我們已經對數組進行了排序。我們找到了滿足條件的第一個數字，所以在這個元素之後的元素也滿足條件，因此我們列印出該元素與N（陣列的大小）的索引之差。
在本文中，我們解決了使用二分搜尋解決大於和不小於的查詢問題。我們也學習了這個問題的C 程序以及我們解決這個問題的完整方法（普通和高效）。我們可以用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望您覺得這篇文章有幫助。
以上是使用C++編寫大於和不小於的查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！
