lower_bound and upper_bound in C++

Lesson 2 of 4 · Binary search

The <algorithm> library has ready-made functions for binary search. With them, in one line you can find the first occurrence, the number of occurrences, the number of elements in an interval or the closest element – without mistakes with the bounds.

Before you start: prerequisites – binary search, the sort function.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Three functions

For a sorted array (or vector) and a value x:

FunctionReturnsExample: a = 1 3 3 3 7 9, x = 3
lower_bound(b, e, x)the first element >= xposition 1
upper_bound(b, e, x)the first element > xposition 4
binary_search(b, e, x)true if x existstrue

lower_bound and upper_bound return an iterator (a pointer to an element). We get the position by subtracting the beginning: lower_bound(v.begin(), v.end(), x) - v.begin(). If there is no such element, they return end(), that is, the position n.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {1, 3, 3, 3, 7, 9};
    int x = 3;
    int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
    int ub = upper_bound(a.begin(), a.end(), x) - a.begin();
    cout << "the first >= 3 is at position " << lb << endl;
    cout << "the first > 3 is at position " << ub << endl;
    cout << "the number of threes: " << ub - lb << endl;
    cout << "is there a 5? " << (binary_search(a.begin(), a.end(), 5) ? "yes" : "no") << endl;
    cout << "lower_bound for 10: " << lower_bound(a.begin(), a.end(), 10) - a.begin() << endl;
    return 0;
}

Typical queries

QuestionExpression (the array is sorted in ascending order)
How many elements are < x?lower_bound(..., x) - a.begin()
How many elements are <= x?upper_bound(..., x) - a.begin()
How many times does x appear?upper_bound(..., x) - lower_bound(..., x)
How many elements are in [L, R]?upper_bound(..., R) - lower_bound(..., L)
How many elements are >= x?a.end() - lower_bound(..., x)

For an ordinary array, instead of a.begin() and a.end() we write a and a + n.

Example: the closest element

For every query x we look for the element of the array closest to the number x. The candidates are the first element >= x (position p) and the element before it (position p − 1) – everything else is farther away.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main() {
    int n, q;
    cin >> n;
    vector<int> a(n);
    for (int &v : a) cin >> v;
    sort(a.begin(), a.end());
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int p = lower_bound(a.begin(), a.end(), x) - a.begin();
        int closest = -1;
        if (p < n) closest = a[p];                                     // the first >= x
        if (p > 0 && (closest == -1 || x - a[p - 1] <= closest - x)) closest = a[p - 1];  // the previous one (the smaller one at an equal distance)
        cout << closest << "\n";
    }
    return 0;
}

Example

Input

5
1 4 9 15 20
3
6
12
25

Output

4
9
20

For 12 both 9 and 15 are at the distance 3, so the smaller one, 9, is printed.

Notes

  • The array must be sorted in the same order that the function expects (ascending by default). For an array sorted in descending order, lower_bound(b, e, x, greater<int>()) is used.
  • It also works on a vector of pairs and of strings: lower_bound(v.begin(), v.end(), make_pair(x, -1)).
  • The containers set and map have their own methods s.lower_bound(x) – they are fast, while lower_bound(s.begin(), s.end(), x) on a set is slow (O(n)).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

Numbers in an interval

n numbers and q queries of the form L R are given (1 ≤ n, q ≤ 105). For every query print how many numbers are in the interval [L, R].

Example

Input

6
5 1 9 3 3 7
3
3 7
10 20
1 9

Output

4
0
6
TASK 02Difficulty: medium

Pairs with a sum of at most S

n numbers (1 ≤ n ≤ 105) and a number S are given. How many pairs of positions i < j are there for which a[i] + a[j] <= S?

Example

Input

5 10
2 7 5 3 9

Output

5
Common mistakes and tips
  • The array must be sorted before the call.
  • The result is an iterator; you get the position by subtracting a.begin().
  • Before reading a[p] check that p < n – if the element you are looking for does not exist, p is n.

Check your knowledge

Open the quiz

lower_bound and upper_bound

1. What does lower_bound return for the value x?




2. How is the number of occurrences of x in a sorted array calculated?




3. What does lower_bound return if all the elements are smaller than x?