# Queries for greater than and not less than

• Difficulty Level : Medium
• Last Updated : 26 Mar, 2021

Given an array of N integers. There will be Q queries, each include two integer of form q and x, 0 <= q <= 1. Queries are of two types:

• In first query (q = 0), the task is to find count of integers which are not less than x (OR greater than or equal to x).

• In second query (q = 1), the task is to find count of integers greater than x.

Examples:

```Input : arr[] = { 1, 2, 3, 4 } and Q = 3
Query 1: 0 5
Query 2: 1 3
Query 3: 0 3
Output :0
1
2
Explanation:
x = 5, q = 0 : There are no elements greater than or equal to it.
x = 3, q = 1 : There is one element greater than 3 which is 4.
x = 3, q = 0 : There are two elements greater than or equal to 3.```

Method 1: A Naive approach can be for each query, traverse the whole array and count integers less or greater than x, depending on q. Time Complexity for this approach will be O(Q*N).
Method 2: An efficient approach can be sort the array and use binary search for each query. This will take O(NlogN + QlogN).
Below is the implementation of this approach :

## C++

 `// C++ to find number of integer less or greater given``// integer queries``#include``using` `namespace` `std;` `// Return the index of integer which are not less than x``// (or greater than or equal to x)``int` `lower_bound(``int` `arr[], ``int` `start, ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>1;``        ``if` `(arr[mid] >= x)``            ``end = mid;``        ``else``            ``start = mid + 1;``    ``}` `    ``return` `start;``}` `// Return the index of integer which are greater than x.``int` `upper_bound(``int` `arr[], ``int` `start, ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>1;``        ``if` `(arr[mid] <= x)``            ``start = mid + 1;``        ``else``            ``end = mid;``    ``}` `    ``return` `start;``}` `void` `query(``int` `arr[], ``int` `n, ``int` `type, ``int` `x)``{``    ``// Counting number of integer which are greater than x.``    ``if` `(type)``        ``cout << n - upper_bound(arr, 0, n, x) << endl;` `    ``// Counting number of integer which are not less than x``    ``// (Or greater than or equal to x)``    ``else``        ``cout << n - lower_bound(arr, 0, n, x) << endl;``}` `// Driven Program``int` `main()``{``    ``int` `arr[] = { 1, 2, 3, 4 };``    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);` `    ``sort(arr, arr + n);` `    ``query(arr, n, 0, 5);``    ``query(arr, n, 1, 3);``    ``query(arr, n, 0, 3);` `    ``return` `0;``}`

## Java

 `// Java to find number of integer``// less or greater given``// integer queries``import` `java.util.Arrays;``class` `GFG``{``// Return the index of integer``// which are not less than x``// (or greater than or equal``// to x)``static` `int` `lower_bound(``int` `arr[], ``int` `start,``                            ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>``1``;``        ``if` `(arr[mid] >= x)``            ``end = mid;``        ``else``            ``start = mid + ``1``;``    ``}` `    ``return` `start;``}` `// Return the index of integer``// which are greater than x.``static` `int` `upper_bound(``int` `arr[], ``int` `start, ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>``1``;``        ``if` `(arr[mid] <= x)``            ``start = mid + ``1``;``        ``else``            ``end = mid;``    ``}` `    ``return` `start;``}` `static` `void` `query(``int` `arr[], ``int` `n, ``int` `type, ``int` `x)``{``    ``// Counting number of integer``    ``// which are greater than x.``    ``if` `(type==``1``)``        ``System.out.println(n - upper_bound(arr, ``0``, n, x));` `    ``// Counting number of integer which``    ``// are not less than x (Or greater``    ``// than or equal to x)``    ``else``        ``System.out.println(n - lower_bound(arr, ``0``, n, x));``}` `// Driver code``public` `static` `void` `main (String[] args)``{``    ``int` `arr[] = { ``1``, ``2``, ``3``, ``4` `};``    ``int` `n = arr.length;` `    ``Arrays.sort(arr);` `    ``query(arr, n, ``0``, ``5``);``    ``query(arr, n, ``1``, ``3``);``    ``query(arr, n, ``0``, ``3``);``}``}` `// This code is contributed by Anant Agarwal.`

## Python3

 `# Python3 program to find number of integer``# less or greater given integer queries` `# Return the index of integer ``# which are not less than x``# (or greater than or equal to x)``def` `lower_bound(arr, start, end, x):` `    ``while` `(start < end):``    ` `        ``mid ``=` `(start ``+` `end) >> ``1``        ``if` `(arr[mid] >``=` `x):``            ``end ``=` `mid``        ``else``:``            ``start ``=` `mid ``+` `1``    ` `    ``return` `start` `# Return the index of integer``# which are greater than x.``def` `upper_bound(arr, start, end, x):` `    ``while` `(start < end):``    ` `        ``mid ``=` `(start ``+` `end) >> ``1``        ``if` `(arr[mid] <``=` `x):``            ``start ``=` `mid ``+` `1``        ``else``:``            ``end ``=` `mid``    ` `    ``return` `start` `def` `query(arr, n, ``type``, x):` `    ``# Counting number of integer``    ``# which are greater than x.``    ``if` `(``type` `=``=` `1``):``        ``print``(n ``-` `upper_bound(arr, ``0``, n, x))` `    ``# Counting number of integer``    ``# which are not less than x``    ``# (Or greater than or equal to x)``    ``else``:``        ``print``(n ``-` `lower_bound(arr, ``0``, n, x))` `# Driver code``arr ``=` `[ ``1``, ``2``, ``3``, ``4` `]``n ``=``len``(arr)` `arr.sort()` `query(arr, n, ``0``, ``5``)``query(arr, n, ``1``, ``3``)``query(arr, n, ``0``, ``3``)` `# This code is contributed by Anant Agarwal.`

## C#

 `// C# to find number of integer less``// or greater given integer queries``using` `System;` `class` `GFG {``    ` `// Return the index of integer which are``// not less than x (or greater than or``// equal to x)``static` `int` `lower_bound(``int` `[]arr, ``int` `start,``                             ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>1;``        ``if` `(arr[mid] >= x)``            ``end = mid;``        ``else``            ``start = mid + 1;``    ``}` `    ``return` `start;``}` `// Return the index of integer``// which are greater than x.``static` `int` `upper_bound(``int` `[]arr, ``int` `start,``                             ``int` `end, ``int` `x)``{``    ``while` `(start < end)``    ``{``        ``int` `mid = (start + end)>>1;``        ``if` `(arr[mid] <= x)``            ``start = mid + 1;``        ``else``            ``end = mid;``    ``}` `    ``return` `start;``}` `static` `void` `query(``int` `[]arr, ``int` `n, ``int` `type, ``int` `x)``{``    ``// Counting number of integer``    ``// which are greater than x.``    ``if` `(type==1)``        ``Console.WriteLine(n - upper_bound(arr, 0, n, x));` `    ``// Counting number of integer which``    ``// are not less than x (Or greater``    ``// than or equal to x)``    ``else``        ``Console.WriteLine(n - lower_bound(arr, 0, n, x));``}` `// Driver code``public` `static` `void` `Main ()``{``    ``int` `[]arr = {1, 2, 3, 4};``    ``int` `n = arr.Length;` `    ``Array.Sort(arr);` `    ``query(arr, n, 0, 5);``    ``query(arr, n, 1, 3);``    ``query(arr, n, 0, 3);``}``}` `// This code is contributed by vt_m.`

## PHP

 `> 1;``        ``if` `(``\$arr``[``\$mid``] >= ``\$x``)``            ``\$end` `= ``\$mid``;``        ``else``            ``\$start` `= ``\$mid` `+ 1;``    ``}` `    ``return` `\$start``;``}` `// Return the index of integer``// which are greater than x.``function` `upper_bound(``\$arr``, ``\$start``, ``\$end``, ``\$x``)``{``    ``while` `(``\$start` `< ``\$end``)``    ``{``        ``\$mid` `= (``\$start` `+ ``\$end``) >> 1;``        ``if` `(``\$arr``[``\$mid``] <= ``\$x``)``            ``\$start` `= ``\$mid` `+ 1;``        ``else``            ``\$end` `= ``\$mid``;``    ``}` `    ``return` `\$start``;``}` `function` `query(``\$arr``, ``\$n``, ``\$type``, ``\$x``)``{``    ` `    ``// Counting number of integer``    ``// which are greater than x.``    ``if` `(``\$type``)``        ``echo` `\$n` `- upper_bound(``\$arr``, 0, ``\$n``, ``\$x``) ,``"\n"``;` `    ``// Counting number of integer``    ``// which are not less than x``    ``// (Or greater than or equal to x)``    ``else``        ``echo` `\$n` `- lower_bound(``\$arr``, 0, ``\$n``, ``\$x``) ,``"\n"``;``}` `    ``// Driver Code``    ``\$arr` `= ``array``(1, 2, 3, 4);``    ``\$n` `= ``count``(``\$arr``);` `    ``sort(``\$arr``);` `    ``query(``\$arr``, ``\$n``, 0, 5);``    ``query(``\$arr``, ``\$n``, 1, 3);``    ``query(``\$arr``, ``\$n``, 0, 3);` `// This code is contributed by anuj_67.``?>`

## Javascript

 ``

Output:

```0
1
2```

Time Complexity : O( (N + Q) * logN).

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

My Personal Notes arrow_drop_up