В данной статье мы рассмотрим один из самых полезных алгоритмов - бинарный поиск. Его суть в следующем: пусть нам задан отрезок \([l;r]\), где \(l\) - левая граница, а \(r\) - правая. Наша задача - найти в этом отрезке заданное число \(A\). Если же такого числа нет, то нужно найти ближайшее число в пределах допустимой погрешности. Вместо отрезка можно использовать массив, отсортированный по возрастанию. Бинарный поиск позволяет решить эту задачу за \(O(\log n)\).

Как работает бинарный поиск

Идея бинарного поиска заключается в том, чтобы поддерживать некоторый промежуток значений \(x\), который точно содержит искомое значение. Далее нам нужно данный промежуток сужать до одного элемента (в случае с массивом), или до числа в пределах погрешности.

Сужение выполняется следующим образом: нам нужно взять среднюю точку отрезка: \(m = \frac{l+r}{2}\). Теперь нам нужно сравнить A и m.

  • Если \(A < m\), то нас не интересует больше промежуток \([m,r]\), ведь там точно нет искомого значения. Переходим к рассмотрению промежутка \([l,m]\).
  • Если \(A > m\), ситуация аналогичная, только теперь переходим к рассмотрению промежутка \([m,r]\).
  • Если \(A = m\), то мы нашли искомое значение: \(A = m\).

Реализация

Разработаем функцию бинарного поиска. Функция binsearch принимает как аргументы массив, его размер, и значение, которое требуется найти.

int binsearch(int arr[], int size, int val)
{
	int l = 0, r = size - 1;
	while (r > l)
	{
		int m = (r + l) / 2;
		if (arr[m] < val)
			l = m + 1;
		else if (arr[m] > val)
			r = m - 1;
		else
			return m;
    }
	if (arr[l] == val) {
		return l;
	}
	else {
		return -1; // если элемент не найден
	}
}

В стандартной библиотеке C++ уже имеется 3 готовых алгоритма для бинарного поиска. Для того, чтобы их использовать нужно подключить заголовочный файл algorithm. Определения этих функций выгледят следующим образом:

std::lower_bound(iterator begin, iterator end, int value);

std::upper_bound(iterator begin, iterator end, int value);

std::binary_search(iterator begin, iterator end, int value);

lower_bound возвращает указатель на первый элемент, больший либо равный value. upper_bound возвращает указатель на элемент, строго больший value, binary_search возвращает тип bool, который равен true, если элемент value был найден, иначе - false.

!!! Кроме того, для того, чтобы работать с данными функциями, массив, на котором будет проводится работа, должен быть отсортирован, иначе данные функции будут возвращать некорректные значения

Рассмотрим следующий код:

int a[20] = { 1,2,3,4,5,6,7,7,7,8,9,9,11,11,12,16,20,20,20,20 };
int* p = lower_bound(a, a + 20, 9);
int* f = upper_bound(a, a + 20, 16);
cout << *p << endl;
cout << *f << endl;

p - указатель, в данном случае он указывает на первый элемент больший, либо равный 9. (Очевидно, это 9). Указатель f соответственно указывает на первый элемент сторого больший, чем 16 (это 20).

Также эти функции можно использовать с STL:

set<int> s;
for (int i = 0; i <=10; i+=2)
	s.insert(i);
auto it = s.lower_bound(2);
cout << *it << endl;

Практическое применение

В математике не для всех уравнений можно получить аналитическое решение. Если аналитически уравнение решить нельзя, приходится искать приближенное решение. Здесь для нас важно понятие погрешности, в пределах которой мы будем искать решение. Такой подход называют численным методом. Если нам известны границы отрезка, на котором находится решение, мы можем применить бинарный поиск (или, как его еще называют, метод бисекции).

Предположим, нам необходимо решить уравнение: \(0.1e^x + \sin 5x = 0\)

Понятно, что аналитически данное уравнение решить не получится, поэтому прибегнем к численным методам. Возьмем точность \(10^{-6}\). В качестве границ возьмем 0 и 1,5.

double f(double x)
{
	return 0.1 * exp(x) + sin(5*x);
}
int main()
{
	double left = 0, right = 1.5;
	while (right - left > 1.e-6)
	{
		double mid = (left + right) / 2.0;
		if (f(left) * f(mid) <= 0)
			right = mid;
		else
			left = mid;
	}
	cout.precision(5);
	cout << std::fixed << (left + right) / 2;
	return 0;
}