Бинарный поиск
В этом занятии мы разбираем, что такое бинарный поиск, почему он работает и как применять его не только для поиска числа в отсортированном массиве, но и для работы с монотонными функциями. Затем переходим к классическим задачам на бинарный поиск: ищем ближайший элемент слева и справа, отвечаем на запросы и пишем решения на C++. Обсуждаем асимптотику, реализацию бинарного поиска на диапазонах и типичные тонкости, из-за которых в этом алгоритме легко ошибиться. В конце показываем, как использовать стандартные алгоритмы C++: lower_bound, upper_bound, equal_range и binary_search. Тайм-коды: 00:00:00 Что такое бинарный поиск 00:01:20 Пример задачи: поиск значения обратной к монотонно возрастающей функции 00:08:10 Поиск числа в отсортированном массиве 00:18:40 Асимптотическая оценка числа операций 00:30:55 Продолжаем поиск числа в отсортированном массиве 00:36:20 Реализация бинарного поиска на диапазонах 00:47:23 Возвращаемся к примеру с обратной функцией 00:57:15 Задача "А. Двоичный поиск" 01:00:10 Решение на C++ 01:07:38 Задача "B. Ближайшее слева" 01:18:37 Задача "C. Ближайшее справа" 01:21:45 Задача "C. Запросы на поедание конфет" 01:28:48 Решение на C++ 01:42:50 Алгоритмы lower_bound, upper_bound, equal_range и binary_search в C++ 01:56:40 Задача "D. Быстрый поиск в массиве" через стандартные алгоритмы в C++ 02:01:00 Заключение
В этом занятии мы разбираем, что такое бинарный поиск, почему он работает и как применять его не только для поиска числа в отсортированном массиве, но и для работы с монотонными функциями. Затем переходим к классическим задачам на бинарный поиск: ищем ближайший элемент слева и справа, отвечаем на запросы и пишем решения на C++. Обсуждаем асимптотику, реализацию бинарного поиска на диапазонах и типичные тонкости, из-за которых в этом алгоритме легко ошибиться. В конце показываем, как использовать стандартные алгоритмы C++: lower_bound, upper_bound, equal_range и binary_search. Тайм-коды: 00:00:00 Что такое бинарный поиск 00:01:20 Пример задачи: поиск значения обратной к монотонно возрастающей функции 00:08:10 Поиск числа в отсортированном массиве 00:18:40 Асимптотическая оценка числа операций 00:30:55 Продолжаем поиск числа в отсортированном массиве 00:36:20 Реализация бинарного поиска на диапазонах 00:47:23 Возвращаемся к примеру с обратной функцией 00:57:15 Задача "А. Двоичный поиск" 01:00:10 Решение на C++ 01:07:38 Задача "B. Ближайшее слева" 01:18:37 Задача "C. Ближайшее справа" 01:21:45 Задача "C. Запросы на поедание конфет" 01:28:48 Решение на C++ 01:42:50 Алгоритмы lower_bound, upper_bound, equal_range и binary_search в C++ 01:56:40 Задача "D. Быстрый поиск в массиве" через стандартные алгоритмы в C++ 02:01:00 Заключение