Module: STL algorithms


Problem

2/6

lower_bound/upper_bound

Theory Click to read/hide

lower_bound and upper_bound are built-in binary search functions.

lower_bound - a function that, in logarithmic time, finds the smallest element in a sorted array that is greater than or equal to the given value k.
It takes the bounds of the array and the value of k as arguments.
Returns an iterator to the found element, or to the end (not included) of the array if no such element exists.
You can read more in the documentation.

upper_bound - a function that in logarithmic time in a sorted array finds the smallest element that is strictly greater than the given value k.
It takes the bounds of the array and the value of k as arguments.
Returns an iterator to the found element, or to the end (not included) of the array if no such element exists.
You can read more in documentation.

It is worth clarifying that the use of these functions on a set or multiset does not work in logarithmic time due to the lack of iterators in the above random access collections.
However, these collections have corresponding built-in methods (that is, you need to use them "through a dot").

Examples:
  vector a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = lower_bound(a.begin(), a.end(), 4); // *it == 5 it = lower_bound(a.begin(), a.end(), 5); // *it == 5 it = lower_bound(a.begin(), a.end(), 8); // it == a.end() it = upper_bound(a.begin(), a.end(), 4); // *it == 5 it = upper_bound(a.begin(), a.end(), 5); // *it == 7 it = upper_bound(a.begin(), a.end(), -1); // *it == 0 // by subtracting iterators, you can get the index of the found element int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // need to use methods instead of functions for set and similar collections set s{ 1, 3, 5 }; set::iterator sit; sit = s.lower_bound(3); // *sit == 3 sit = s.upper_bound(3); // *sit == 5  

Problem

You are given an ordered array A of n natural numbers. 
There are q requests to be processed. Each query is given two parameters - its type ti and the number ki.

Description of queries by their type:
1) Find in A the minimum number that is not less than ki.
2) Find the minimum number in A that is strictly greater than ki.
3) Find in A the maximum number that is not greater than ki.
4) Find the maximum number in A that is strictly less than ki.

For each query, report the number found, or -1 if none exists.

Input:
The first line contains number n (1 <= n <= 105) - the number of elements of array A.
The second line contains n natural numbers Ai (1 <= Ai <= 109) - the array elements themselves. Moreover, for all i < n done Ai <= Ai+1.
The third line contains the number q (1 <= q <= 105) - the number of requests.
The next q lines contain two numbers each - ti (1 <= ti <= 4) and ki (1 < ;= ki <= 109).

Output:
Print q lines, i-th one number - the answer to the i-th query.

Examples:
 
Input Output
4
3 5 5 7
4
15
27
3 2
4 4		 5
-1
-1
3

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
int query1(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query2(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query3(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *(--it);
}

int query4(vector<int>& arr, int k) {
	vector<int>::iterator it =   
if (it ==     
)
		return -1;
	return *(--it);
}
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int q;
	cin >> q;

	while (q--) {
		int type, k;
		cin >> type >> k;

		if (type == 1)
			cout << query1(arr, k) << endl;
		if (type == 2)
			cout << query2(arr, k) << endl;
		if (type == 3)
			cout << query3(arr, k) << endl;
		if (type == 4)
			cout << query4(arr, k) << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!