#11 C++ Жемчужины STD - Бинарный поиск
00:04 Введение в бинарный поиск -Приветствие и анонс темы видео: бинарный поиск. -Упоминание о трёх разделах алгоритмов, работающих с отсортированными -диапазонами. -Объяснение, что бинарный поиск — один из первых алгоритмов для изучения. 00:45 Линейный поиск -Описание линейного поиска с использованием std::find. -Пример поиска элемента со значением 40. -Временная сложность линейного поиска: линейно пропорциональна размеру контейнера. 01:50 Принцип бинарного поиска -Начало поиска с середины отсортированного контейнера. -Исключение половины элементов на каждом шаге. -Рекурсивное повторение процесса для меньшего диапазона. 03:30 Временная сложность бинарного поиска -Объяснение экспоненциальной зависимости количества шагов от размера контейнера. -Формула для вычисления сложности: log 2 n. -Пример сравнения производительности: поиск в массиве из 10 миллионов элементов. 04:27 Анимация бинарного поиска -Демонстрация работы бинарного поиска на примере поиска значения 611. -Объяснение раннего выхода при бинарном поиске. 05:31 Операции бинарного поиска в стандартной библиотеке -Описание операций бинарного поиска: бинарный поиск, нижняя граница, верхняя граница, равный диапазон. -Различие между бинарным поиском и другими операциями. -Примеры использования нижней и верхней границы для поиска диапазона значений. 09:35 Тестирование операций бинарного поиска -Создание вектора с 100 миллионами элементов и их сортировка. -Выбор цели для поиска примерно в середине контейнера. -Запуск алгоритмов поиска с параллелизмом для повышения производительности. 10:33 Параллелизм в стандартной библиотеке -Возможность включения параллелизма для алгоритмов в стандартной библиотеке. -Тизер будущего эпизода о параллельном выполнении алгоритмов. 11:46 Сравнение линейного и двоичного поиска -Линейный поиск занимает около 18 миллисекунд. -Двоичный поиск выполняется за одну микросекунду, что в 18 000 раз быстрее. -Особенности аппаратного обеспечения влияют на реальное ускорение. 12:57 Преимущества двоичного поиска -Двоичный поиск значительно быстрее линейного для отсортированных диапазонов. -Использование нижней границы для поиска первого элемента может быть в два раза быстрее. -Для поиска всего диапазона лучше использовать равный диапазон. 13:52 Пример использования нижней границы -Создание алгоритма для поиска индекса значения в отсортированном контейнере. -Контейнер должен поддерживать сравнение «меньше чем равно». -Возврат необязательного параметра для обозначения отсутствия элемента. 14:47 Реализация алгоритма -Использование const container для доступа только для чтения. -Определение типа значения контейнера и передача его по ссылке. -Проверка наличия элемента в контейнере и возврат индекса или необязательного параметра. 16:34 Тестирование алгоритма -Функция find возвращает необязательный параметр: true при наличии значения, false при отсутствии. -Тестирование алгоритма на примере поиска значения 5 и 7. -Исправление ошибок с необязательными параметрами и типами. 17:36 Заключение -Подведение итогов: использование нижней границы для бинарного поиска. -Возможность адаптации алгоритма под конкретные потребности. -Призыв к зрителям делиться идеями в комментариях и ставить лайки.
00:04 Введение в бинарный поиск -Приветствие и анонс темы видео: бинарный поиск. -Упоминание о трёх разделах алгоритмов, работающих с отсортированными -диапазонами. -Объяснение, что бинарный поиск — один из первых алгоритмов для изучения. 00:45 Линейный поиск -Описание линейного поиска с использованием std::find. -Пример поиска элемента со значением 40. -Временная сложность линейного поиска: линейно пропорциональна размеру контейнера. 01:50 Принцип бинарного поиска -Начало поиска с середины отсортированного контейнера. -Исключение половины элементов на каждом шаге. -Рекурсивное повторение процесса для меньшего диапазона. 03:30 Временная сложность бинарного поиска -Объяснение экспоненциальной зависимости количества шагов от размера контейнера. -Формула для вычисления сложности: log 2 n. -Пример сравнения производительности: поиск в массиве из 10 миллионов элементов. 04:27 Анимация бинарного поиска -Демонстрация работы бинарного поиска на примере поиска значения 611. -Объяснение раннего выхода при бинарном поиске. 05:31 Операции бинарного поиска в стандартной библиотеке -Описание операций бинарного поиска: бинарный поиск, нижняя граница, верхняя граница, равный диапазон. -Различие между бинарным поиском и другими операциями. -Примеры использования нижней и верхней границы для поиска диапазона значений. 09:35 Тестирование операций бинарного поиска -Создание вектора с 100 миллионами элементов и их сортировка. -Выбор цели для поиска примерно в середине контейнера. -Запуск алгоритмов поиска с параллелизмом для повышения производительности. 10:33 Параллелизм в стандартной библиотеке -Возможность включения параллелизма для алгоритмов в стандартной библиотеке. -Тизер будущего эпизода о параллельном выполнении алгоритмов. 11:46 Сравнение линейного и двоичного поиска -Линейный поиск занимает около 18 миллисекунд. -Двоичный поиск выполняется за одну микросекунду, что в 18 000 раз быстрее. -Особенности аппаратного обеспечения влияют на реальное ускорение. 12:57 Преимущества двоичного поиска -Двоичный поиск значительно быстрее линейного для отсортированных диапазонов. -Использование нижней границы для поиска первого элемента может быть в два раза быстрее. -Для поиска всего диапазона лучше использовать равный диапазон. 13:52 Пример использования нижней границы -Создание алгоритма для поиска индекса значения в отсортированном контейнере. -Контейнер должен поддерживать сравнение «меньше чем равно». -Возврат необязательного параметра для обозначения отсутствия элемента. 14:47 Реализация алгоритма -Использование const container для доступа только для чтения. -Определение типа значения контейнера и передача его по ссылке. -Проверка наличия элемента в контейнере и возврат индекса или необязательного параметра. 16:34 Тестирование алгоритма -Функция find возвращает необязательный параметр: true при наличии значения, false при отсутствии. -Тестирование алгоритма на примере поиска значения 5 и 7. -Исправление ошибок с необязательными параметрами и типами. 17:36 Заключение -Подведение итогов: использование нижней границы для бинарного поиска. -Возможность адаптации алгоритма под конкретные потребности. -Призыв к зрителям делиться идеями в комментариях и ставить лайки.