Функция lower_bound

Функция lower_bound из заголовочного файла algorithm выполняет бинарный поиск в отсортированном диапазоне и возвращает итератор на первый элемент, который не меньше заданного значения. В первый параметр мы передаем итератор начала диапазона, во второй - итератор конца диапазона, а в третий - значение, с которым сравниваются элементы. Диапазон должен быть отсортирован по возрастанию, иначе поведение функции не определено.

Если все элементы меньше заданного значения, функция возвращает итератор конца диапазона. Функция работает за логарифмическое время O(log n), так как использует бинарный поиск.

Синтаксис

lower_bound(first, last, value)
lower_bound(first, last, value, comp)

Пример

Давайте найдем первый элемент вектора, который не меньше 3:

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

int main()
{
	vector<int> v = {1, 2, 3, 4, 5};
	auto it = lower_bound(v.begin(), v.end(), 3);
	
	if (it != v.end()) {
		cout << *it << endl;
	} else {
		cout << "not found" << endl;
	}
	
	return 0;
}

Результат выполнения кода:

3

Пример

Давайте найдем первый элемент вектора, который не меньше 6. Так как все элементы меньше 6, функция вернет итератор конца:

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

int main()
{
	vector<int> v = {1, 2, 3, 4, 5};
	auto it = lower_bound(v.begin(), v.end(), 6);
	
	if (it != v.end()) {
		cout << *it << endl;
	} else {
		cout << "not found" << endl;
	}
	
	return 0;
}

Результат выполнения кода:

"not found"

Пример

Давайте найдем позицию первого элемента, который не меньше 3, используя разность итераторов:

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

int main()
{
	vector<int> v = {1, 2, 3, 4, 5};
	auto it = lower_bound(v.begin(), v.end(), 3);
	int pos = it - v.begin();
	
	cout << pos << endl;
	
	return 0;
}

Результат выполнения кода:

2

Смотрите также

функция upper_bound,
которая находит первый элемент, больший заданного значения
функция binary_search,
которая проверяет наличие элемента в отсортированном диапазоне
функция equal_range,
которая возвращает пару итераторов для заданного значения
функция find,
которая ищет элемент в диапазоне