Query for finding the first integer from the array which is less than or equal to X using C++ STL.

Given an array of integers arr[] of length N and Q total number of queries. In each query given an integer X. For each query output first integer from the array, which is less than or equal to X. In other words, find the largest integer which is less than or equal to X.

If the answer of the ith query is Yi, then Yi should be present in arr[] and the largest integer from array such that Yi<=Xi.

Else if such integer does not exist output "NO".

Read Also:All Sorting Algorithm In python

Example:

Input:

N = 8//size of array

Q = 4//Number of query asked

arr[] = {1,9,8,7,8,2,3,5}

query[] = {4,6,0,9}

Output:

3

5

NO

9

Explanation:

First query X = 4, 3 is the first integer which is less than 4.

Second query X = 6, 5 is the first integer which is less than 6.

Thord query X = 0, no such integer exists in the array which is less than or equal to 0.

Fourth query X = 9, 9 is the first integer which is equal to 9.

Naive Approach: 

1. In each query Travers, the whole array arr[] and find the largest integer which is less than or equal to X.
2. If an answer exists output that else outputs "NO".

Time Complexity: O(N*Q)

Auxiliary Space: O(N+Q)

Optimal Approach:

prerequisites : std::lower_bound C++ STL

The lower bound C++ function returns an iterator pointing to an element greater than or equal to a given element.

proceed below steps for Q queries.

Step:

1. To use the lower bound function for less than purpose multiply each integer of arr[] multiply by -1. (store opposite values in arr[])
2. Sort the array in ascending order.
3. Use lower bound function on arr[] with -X argument.
4. If function returns arr.end() iterator. output "NO".
5. Else output integer with the opposite sign which is pointed by this iterator.

For each query :

vector<int>::iterator j = lower_bound(arr.begin(), arr.end(), -X);

if(j == arr.end()) {

    cout << "NO" << endl;

} else {

    cout << -1 * (*j) << endl;

}

(also we can use the upper bound function for only less than X purpose.)

Here, the Time Complexity of the Lower_bound function on the sorted array is O(logN).

Implementation.cpp

/*

C++ program: 

Query for finding the first integer from the array which 

is less than or equal to X using C++ STL.

*/

#include <bits/stdc++.h>

using namespace std;

// Driver fuction

int main()

{

    int N = 9; //size of array.

    int Q = 6; //Number of queries.

    // input array.

    vector<int> arr = {-1, 9, 8, 7, 8, 2, 3, 5, -5};

    // asked queries.

    vector<int> query = {4, 6, 0, 9, -1, -8};

    //store opposite values in array.

    //multiplying by -1

    for (int i = 0; i < N; i++)

    {

        arr[i] *= -1;

    }

    // Sort the array in ascending order.

    sort(arr.begin(), arr.end());

    //proceeding Q queries.

    for (int i = 0; i < Q; i++)

    {

        int X = query[i];

        //declaration of vector<int> iterator

        vector<int>::iterator j;

        //Use lower bound function on arr[] with -X argument.

        j = lower_bound(arr.begin(), arr.end(), -X);

        if (j == arr.end()) //integer does not exist.

        {

            cout << "NO" << endl;

        }

        else //integer exists

        {

            cout << -1 * (*j) << endl;

        }

    }

    return 0;

}

Time Complexity: O(N+Q*logN)

Auxiliary Space: O(N+Q)

Read Also: All Sorting Algorithm In C++

Read Also:Merge Sort Algorithm