Лекция: бинарный поиск

Задачи на CF: https://codeforces.com/group/uQw4LhzOcG/contest/568324 Задачи на Yandex Cup 2024: https://contest.yandex.ru/contest/69390/problems/D Темы: 1) бинарный поиск в отсортированном массиве 2) стандартные функции для бинарного поиска в C++: lower_bound, upper_bound, equal_range, binary_search 3) бинарный поиск на отрезке целочисленной прямой 4) бинарный поиск на отрезке массива начиная с какой-то позиции 5) бинарный поиск по ответу и его применения при упрощении исходной задачи 6) двоичный поиск (по степеням двоек) 7) бинарный поиск в интерактивных задачах 8) бинарный поиск по производной от унимодальной функции Исходный код вы можете найти здесь: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/beginner/binary-search Тайм-коды: 00:00:00 Введение 00:02:22 Задача "Отгадай число" - интерактивный бинпоиск 00:04:15 Что такое бинарный поиск? 00:09:55 Реализация бинарного поиска 00:20:15 Интерактивные задачи и fflush 00:25:25 Бинпоиск в отсортированном массиве 00:31:50 Реализация бинпоиска в массиве 00:32:25 Вопрос: что такое интерактивная задача? 00:35:50 Функции upper_bound, lower_bound, equal_range, binary_search 00:43:30 Когда работают эти функции из C++? 00:52:25 Бинарный поиск на отрезке массива 00:58:45 Бинарный поиск по ответу и упрощение задачи на примере задачи "Максимизация отношения" 01:21:35 Более простой пример на бинпоиск по ответу: задача "Построение аквариума" 01:28:50 Бинарный поиск по производной от унимодальной функции 01:41:15 Двоичный поиск по степеням двойки 01:48:20 На примере задачи "Легенда об Икаре" 02:03:15 Домашнее задание