Writing greater than and not less than queries using C++

In this article, we are given a question, given an array, and there are two types of queries to answer.

• Type 0 - We need to count the number of elements greater than or equal to x (a given value).
• Type 1 - We need to count the number of elements strictly greater than x (given value).

So here is a simple example -

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.

Methods to find the solution

We can use two different methods to find the solution. First we will use a brute force solution and then check if it works for higher constraints. If not, we continue optimizing our solution.

Brute force solution

In this method, we will iterate through the array for all q queries that satisfy the given condition and find the number that satisfies the condition.

Example

#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;
}

Output

0
1
3

In the above method, we just loop through the array and calculate the answer to the query; this method is valid for the given example, but This approach will fail if higher constraints are encountered, since the total time complexity of the program is O(N*Q), where N is the size of the array and Q is the number of queries, so now we will optimize this method to make it applicable to higher constraints.

Efficient method

In this method, we will use binary search to find the upper and lower bounds of a given value. We first sort the array using binary search and then apply our lower and upper bound functions as needed.

Example

#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;
}

Output

0
1
2

The above code uses binary search, which greatly reduces the time complexity. Therefore, our final complexity is O(NlogN), where N is the size of the array.

Explanation of the above code

In this method, we will use binary search to find the upper and lower bounds of a given value. Now for binary search we sort the array first as it only works on sorted array. We create a lower bound and an upper bound function to help us find the first number that satisfies the conditions of type 0 and type 1. Now we have the array sorted. We find the first number that satisfies the condition, so the element after this element also satisfies the condition, so we print out the difference between that element and the index of N (the size of the array).

Conclusion

In this article, we solved the problem of solving greater than and not less than queries using binary search. We also learned the C program for this problem and our complete approach to solving it (both trivial and efficient). We can write the same program in other languages ​​like C, Java, Python and others. Hope you found this article helpful.

The above is the detailed content of Writing greater than and not less than queries using C++. For more information, please follow other related articles on the PHP Chinese website!