Upper & Lower bound

Lower Bound

The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val.
This means that the function returns the index of the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the index of the first such value.
The elements in the range should be sorted.

Syntax 1: 
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, val); 
Syntax 2: 
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, val, Compare comp);

Parameters: The above methods accept the following parameters.

• first, last: The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
• val: Value of the lower bound to be searched for in the range.
• comp: Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return Value: An iterator to the lower bound of val in the range. If all the elements in the range compare less than val, the function returns last. If all the elements in the range are larger than val, the function returns a pointer to the first element.

Example:

vector<int> v{1, 3, 6, 6, 8};
vector<int>::iterator lower1, lower2, lower3;
lower1 = lower_bound(v.begin(), v.end(), 4); // Index will be 2
lower2 = lower_bound(v.begin(), v.end(), 1); // Index will be 0
lower3 = lower_bound(v.begin(), v.end(), 9); // Index will be 5
// To get the index do: lower1 - v.begin();
cout<<"lower_bound for element 4 at position : "<<lower1 - v.begin()<<endl; // 2

Upper Bound

upper_bound() is a standard library function in C++ defined in the header. It returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to val.

Syntax 1:
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, val);
Syntax 2:
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, val, Compare comp);

Parameters: The above methods accept the following parameters.

• first, last: The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
• val: Value of the upper bound to search for in the range.
• comp: Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return type: An iterator to the upper bound of val in the range. If all the element in the range compare less than val, the function returns last.

Example:

vector<int> v{1, 3, 6, 6, 8};
vector<int>::iterator upper1, upper2, upper3;
upper1 = upper_bound(v.begin(), v.end(), 6); // 4
upper2 = upper_bound(v.begin(), v.end(), 1); // 1
upper3 = upper_bound(v.begin(), v.end(), 4); // 2
// To get the index do: upper1 - v.begin(); 
cout<<"upper_bound for element 6 at position : "<<upper1 - v.begin()<<endl; //4

Note: We can also use lower and upper bound on set.

Syntax:

Let s is a set.
s.lower_bound(val);
s.upper_bound(val);

Try the following example in the editor below.

You are given N integers in sorted order not necessarily distinct. Also, you are given Q queries. In each query, you will be given an integer X and you have to tell whether that integer is present in the array. If so, you have to tell at which index (leftmost) it is present and if it is not present, you have to tell the rightmost index at which the current integer can be inserted such that the array remains sorted.

NOTE: You are not required to insert the value in the array. Array is not changed at any point.

Input Format

First line contains an integer N.
Second line contains N space-separarted integer in sorted order.
Third line contains an integer Q, the number of queries.
Each of the next Q lines contain a single integer X.

Output Format

For each query, print the index as described.

Sample Input

6
5 15 21 21 22 22
5
10
21
23
3
22

Sample Output

1
2
6
0
4