使用C++編寫大於和不小於的查詢

在這篇文章中，我們被給定了一個問題，給定了一個數組，並且有兩種類型的查詢需要回答。

• 類型 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 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中文網其他相關文章！