Тренировки по алгоритмам от Яндекса. Лекция 6: «Бинарный поиск»

• Шестая лекция курса по алгоритмам посвящена бинарному поиску.  

• 90% программистов не умеют писать бинарный поиск.  

• Лекция будет состоять из объяснения бинарного поиска, задачи из жизни и тернарного поиска.  

• Бинарный поиск можно сравнить с поиском слова в словаре.  

• Каждый раз область поиска уменьшается вдвое.  

• Это самый быстрый способ найти что-то в упорядоченной последовательности.  

• Пример с функцией, определенной для целых чисел.  

• В словаре нужно найти первое подходящее слово.  

• Левый и правый бинпоски: левое значение функции, когда все становится хорошо, и правое значение, когда все становится слишком большим.  

• Определение минимального и максимального значений функции.  

• Поддержка границ поиска неизменяемыми.  

• Выбор серединки между левой и правой границей и проверка, все ли хорошо.  

• Цикл, который заканчивается, когда и станет равно.  

• Убирается серединка и проверяется, все ли хорошо.  

• Если все хорошо, правая граница заменяется на серединку.  

• Область поиска сокращается вдвое за каждый шаг.  

• Сложность алгоритма - логарифм от количества возможных значений.  

• Логарифм растет медленно, что делает бинарный поиск быстрее линейного.  

• Бин-поиск используется для целых чисел.  

• Функция может возвращать true или false.  

• Параметры функции могут быть дополнительными.  

• Указатели могут не сходиться, что приводит к вечному циклу.  

• Универсальный метод проверки на двух элементах.  

• Пример с двумя элементами показывает, как указатели должны сходиться.  

• Пример реализации бин-поиска без плюс-один.  

• Если функция вернула true, правый указатель сдвигается на m.  

• Если функция вернула false, левый указатель сдвигается на один.  

• Если функция вернула false, указатели не сходятся.  

• Вечный цикл возникает, если указатели не сходятся.  

• Решение: округлять результат деления на два вверх.  

• Удаление плохих значений из отрезка поиска.  

• Алгоритм работает правильно, даже если не поддерживаются плохие значения.  

• Оставление только хороших значений улучшает производительность.  

• Проверка на двух элементах показывает, что округление вверх работает правильно.  

• Округление вниз может привести к схождению на плохой элемент.  

• Важно запомнить эту идею для быстрой проверки и исправления ошибок.  

• Правый бин-поиск ищет последнее подходящее значение.  

• Пример на двух элементах показывает, как указатели сходятся.  

• Если оба значения были хорошими, указатели сходятся к последнему хорошему значению.  

• В Москве проводили тестирование для директоров школ, где решали задачи по разным предметам.  

• Задача касалась управляющего совета школы, где родители должны составлять не менее трети членов.  

• Директора школ часто ошибались, подбирая числа так, чтобы дробь была равна одной трети.  

• Задача имеет конструктивное математическое решение, но мы будем использовать бинарный поиск.  

• Важно учитывать, что при добавлении родителей общее количество членов совета увеличивается.  

• Левая граница поиска может быть равна нулю, а правая граница выбирается с запасом.  

• Левая граница поиска может быть равна нулю, а правая граница выбирается с запасом.  

• Программа использует функцию для проверки, достаточно ли родителей в совете.  

• Если родителей недостаточно, добавляем еще, если достаточно – останавливаемся.  

• Юра решает задачи на Литко, каждый день решая на одну задачу больше.  

• Нужно определить, за сколько дней Юра решит не менее n задач.  

• Задача решается с помощью бинарного поиска по ответу.  

• Юра решает задачи каждый день, и нужно определить, за сколько дней он решит n задач.  

• Используется формула арифметической прогрессии для расчета количества задач.  

• Программа использует бинарный поиск для нахождения минимального количества дней.  

• Михаил читает лекции по алгоритмам, и ему нужно разместить n квадратных стикеров на доске.  

• Задача решается с помощью бинарного поиска, перебирая размеры стикеров.  

• Проверяется, сколько стикеров поместится на доску, и сравнивается с нужным количеством.  

• Рассматривается задача бинарного поиска в отсортированной последовательности чисел.  

• Используется левая и правая границы поиска для нахождения подходящего числа.  

• Если подходящего числа нет, возвращается самое большое число.  

• Вводится дополнительная проверка, чтобы избежать возврата самого большого числа.  

• Проверяется, больше ли текущее число, чем искомое.  

• Если число больше, возвращается индекс первого больше либо равного числа.  

• Код показывает, как реализовать бинарный поиск с дополнительной проверкой.  

• Используется функция для проверки, больше ли текущее число искомого.  

• Возвращается индекс первого больше либо равного числа или длина последовательности, если такого числа нет.  

• Бинарный поиск часто используется для поиска в отсортированных данных.  

• Пример: поиск первого события после сбоя в логе.  

• Линейный поиск не подходит для таких задач из-за высокой сложности.  

• Рассматривается задача подсчета количества вхождений числа в отсортированную последовательность.  

• Неправильное решение: линейный поиск до последнего числа.  

• Правильное решение: использование двух бинарных поисков для нахождения индексов.  

• Используются два бинарных поиска: один для числа больше искомого, другой для числа строго больше.  

• Разница между индексами дает количество вхождений.  

• Важно учитывать, что бинарный поиск не может уйти правее элемента, на который указывает.  

• Бинарный поиск полезен для расчета аннуитетных платежей по ипотеке.  

• Аннуитетный платеж: одинаковая сумма каждый месяц, большая часть которой идет на погашение процентов.  

• Постепенно долг уменьшается, и проценты становятся меньше.  

• Ежемесячный процент не равен годовому проценту, деленному на 12.  

• Используется бинарный поиск для нахождения точного значения.  

• Пример: если процент годовых 12%, то ежемесячный процент будет меньше 12%.  

• Бинарный поиск для вещественных чисел с точностью до эпсилон.  

• Пример: если процент в месяц 1%, то за год сумма составит 1.12%.  

• Важно подобрать точность для точного расчета.  

• Перебор суммы ежемесячного платежа с помощью бинарного поиска.  

• Моделирование процесса погашения кредита.  

• Пример: для кредита в 10 миллионов рублей на 25 лет.  

• Велосипедисты едут с постоянной скоростью, нужно найти момент минимального расстояния между ними.  

• Построение графика положения велосипедистов.  

• Использование бинарного поиска по производной для нахождения минимума функции.  

• Проверка возрастания функции для определения направления поиска.  

• Моделирование положения велосипедистов в каждый момент времени.  

• Использование бинарного поиска для нахождения минимума функции.  

• Рекомендуется писать функции для работы с множествами, как в третьей лекции.  

• Понимание внутреннего устройства структур полезно для программирования.  

• В реальных задачах лучше использовать стандартные множества.  

• Тесты в домашних заданиях могут быть сложными для неоптимизированных решений.  

• Важно оценивать асимптотическую сложность программы.  

• Большие числа операций могут привести к неэффективному решению.  

• Симптотика помогает оценить количество элементарных действий программы.  

• В реальном мире задачи имеют конечные значения, а не бесконечности.  

• Симптотика позволяет сравнивать реальные значения с допустимыми.  

• В бинарном поиске можно уменьшить область поиска, используя результаты первого поиска.  

• Простота реализации часто предпочтительнее сложных оптимизаций.  

• В Python не всегда целесообразно использовать целочисленное деление вместо побитового.  

• Тернарный поиск подходит для поиска минимума или максимума функции.  

• Функция должна сначала убывать, а затем возрастать.  

• Бинарный поиск по производной аналогичен тернарному поиску, но с другими рассуждениями.  

• В чате можно задать новые вопросы.  

• Прошла половина курса, и студенты могут оставить фидбек.  

• Обратная связь поможет улучшить содержание курса.