Слайд 3Алгоритм (для возрастающей функции)
Обозначим левую границу отрезка, на котором мы
ищем заданное значение, как L, а правую – как R.
Посчитаем
точку M = (L+R)/2.
Вычислим значение функции в точке M.
Если это значение меньше искомого, то теперь L = M + EPS, иначе R = M (EPS – точность поиска).
Если R – L > EPS – возвращаемся к первому шагу, иначе поиск окончен.
Результат поиска равен R.
Слайд 10Применение
Поиск значения параметра по значению функции.
Аналогично рассмотренному примеру.
Поиск индекса элемента
в отсортированном массиве.
lower_bound(‘итератор на начало’,’итератор за конец’,’значение’) – возвращает итератор
на первый элемент в диапазоне [‘значение’; +∞)
upper_bound(‘итератор на начало’,’итератор за конец’,’значение’) – возвращает итератор на первый элемент в диапазоне (‘значение’; +∞)
Для set и map эти функции являются методами и принимают только значение.
Поиск по ответу.
