Первое совпадение при любом порядке данных
Сортировка не нужна. Подходит и для упорядоченного массива; проверяет позиции по очереди.
Поиск
Найти игрока с нужным результатом, собрать всех с одинаковыми очками или подобрать минимальную производительность. Учимся выбирать, что именно должен вернуть поиск.
Начнём с таблицы результатов игроков: научимся находить одно совпадение, сочетать разные способы поиска и выделять целую группу. Затем посмотрим, как искать среди возможных ответов и ускорять повторяющиеся запросы.
Для чтения достаточно понимать массив и индекс. Если хочется сначала разобраться, почему один проход растёт как O(N), а деление пополам — как O(log N), посмотрите примеры в Big O.
Данные для сравнения
Выберите набор очков и нажмите на игрока с результатом, который хотите найти. Все примеры поиска по массиву используют этот набор. Его можно менять здесь или через «Общий массив» в любом из примеров.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
В ячейке — очки и иконка класса, под ней — индекс. Имя персонажа видно в подписи текущего шага. Линейный поиск использует исходный порядок, остальные — копию по возрастанию очков. Подготовительная сортировка в счётчики не входит. Можно выбрать до 10 игроков, оставить одного или проверить пустой массив. У мастерской свои параметры.
Линейный поиск
После боя на арене у нас есть результаты игроков. В каждой ячейке — очки игрока и иконка класса его персонажа. Под ячейкой указан индекс — позиция в массиве. Нужно найти одного игрока с заданным результатом. Если такого нет, получим «не найдено» — это обычный ответ. N — число игроков, target — сколько очков мы ищем.
Сравним два алгоритма. Линейный поиск проверяет игроков одного за другим и работает при любом порядке очков, в том числе в отсортированном массиве. Бинарный поиск сокращает область поиска примерно вдвое после каждой проверки; для этого примера ему нужен массив, заранее упорядоченный по очкам.
Проверяем элементы по очереди, пока не найдём совпадение.
В этом примере оставим игроков в порядке регистрации. Сверяем результат воина, затем мага и следующих игроков. Останавливаемся на первом совпадении. Если переставить игроков по возрастанию очков, алгоритм останется тем же: он по-прежнему будет проверять позиции по очереди.
Под ячейкой указан индекс игрока в массиве. Отсчёт начинается с нуля: у первого игрока индекс 0, у второго — 1, у третьего — 2. Именно индекс найденного игрока возвращает этот алгоритм.
Для отсортированных данных можно добавить раннюю остановку. Ищем 15 в [5, 10, 20, 30]: увидев 20, уже знаем, что дальше 15 не встретится. В показанном ниже коде этого условия нет — он работает при любом порядке. Позже используем раннюю остановку в поиске прыжками. Даже с ней поиск в худшем случае может пройти весь массив.
Особенности этого способа
Эта версия возвращает индекс первого совпадения или notFound — «не найдено». Сам массив не меняется.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
Порядок регистрации
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Проверяем элементы по очереди, пока не найдём совпадение.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Первый игрок может сразу подойти: O(1). Совпадение только в конце или отсутствие нужного результата потребуют проверить всех N игроков: O(N). Для показанного алгоритма эти оценки одинаковы и в отсортированном, и в неотсортированном массиве: он проверяет только равенство.
Лучший случайO(1)Худший случайO(N)Дополнительная памятьO(1)
Попробуйте. Выберите «Минимум в конце» и оставьте хотя бы два элемента. Сначала ищите первое число в массиве, затем 1, которая стоит последней. Сравните число посещений. После этого нажмите «Нет в массиве».
Бинарный поиск
Используем порядок значений, чтобы исключать половину оставшихся позиций.
Для этого примера заранее подготовим копию массива: расположим игроков по возрастанию очков. Смотрим на середину: слишком мало очков — продолжаем справа, слишком много — слева. Порядок позволяет исключить сразу половину позиций. При совпадении возвращаем игрока; среди нескольких равных результатов это может быть любой участник группы.
Важен порядок именно по тому полю, которое сравниваем. Список, отсортированный по названию класса, не подходит для этого поиска по очкам. В неупорядоченном массиве значение в середине ничего не говорит о значениях слева и справа: можно отбросить нужного игрока.
Индекс относится к упорядоченной копии: плут с 13 очками теперь стоит на другой позиции. Оставшуюся часть массива будем называть окном поиска.
Как читать границы окна
Квадратная скобка включает границу, круглая — исключает. Это правило действует с обеих сторон. В записи [1, 4) позиция 1 входит в окно, а позиция 4 — уже нет: остаются индексы 1, 2 и 3. Здесь числа обозначают позиции, а не очки игроков.
Окно [1, 4): выделены индексы 1, 2 и 3
Окно [left, right) имеет длину right − left. Поэтому [4, 4) пусто, а [0, N) охватывает весь массив. N — позиция сразу после последнего элемента; элемента с таким индексом нет.
Особенности этого способа
Массив должен быть отсортирован по возрастанию. Сортировка меняет позиции: ответ относится к показанной упорядоченной копии, а не к исходному списку.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Используем порядок значений, чтобы исключать половину оставшихся позиций.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Совпадение в первой середине даёт O(1). В худшем случае число посещений растёт как O(log N). Подготовительная сортировка оценивается отдельно.
Лучший случайO(1)Худший случайO(log N)Дополнительная памятьO(1)
Попробуйте. Выберите «Все значения равны» и оставьте хотя бы два элемента. Нажмите на любого игрока и выполните линейный и бинарный поиск. Посмотрите на классы персонажей: почему оба способа правы, хотя находят разных игроков?
Поиск прыжками
Не обязательно искать одним способом от начала до конца. Можно сначала определить небольшой участок, а затем выбрать, как проверить его содержимое. В следующих двух примерах массив уже отсортирован; различается способ найти этот участок.
Пропускаем целые блоки, затем проверяем один из них по очереди.
Разобьём упорядоченный список игроков на блоки одинакового размера. Посмотрим на последнего игрока первого блока. Если даже у него очков меньше, чем нужно, остальные в этом блоке тоже не подходят. Перепрыгнем к концу следующего блока.
Как только на краю встретится результат не меньше искомого, перестанем прыгать. Теперь последовательно проверим игроков внутри этого блока. При совпадении вернём индекс; если очки уже больше цели, остановимся без ответа — дальше они не уменьшаются.
Это сочетание двух приёмов: сначала грубо сужаем область, затем проверяем её подробно. Обычный бинарный поиск в массиве обычно требует меньше посещений; прыжки здесь показывают другой способ использовать порядок. Размер блока выбираем около квадратного корня из числа элементов: для 16 игроков это 4.
Особенности этого способа
Нужен массив по возрастанию очков. sqrt — квадратный корень, floor — округление вниз. Последний блок может быть короче остальных. При переборе край блока иногда проверяется повторно; счётчик учитывает каждое посещение.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Пропускаем целые блоки, затем проверяем один из них по очереди.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Если цель находится в начале первого блока, достаточно постоянного числа посещений: O(1). В худшем случае проверяем края примерно √N блоков и затем до √N элементов одного блока: O(√N). Подготовительная сортировка в оценку не входит.
Лучший случайO(1)Худший случайO(√N)Дополнительная памятьO(1)
Попробуйте. Выберите «Минимум в конце», установите 10 элементов и ищите 8. Проследите, как поиск пропускает два блока, затем переключается на перебор третьего. Сравните с бинарным поиском на тех же данных.
Поиск с удвоением
После проверки первого элемента идём к позициям 1, 2, 4, 8… и только потом переходим к бинарному поиску.
Иногда нужная позиция находится близко к началу длинной упорядоченной последовательности. Вместо её середины начнём с маленького окна и будем расширять его. Остановимся, когда значение на проверяемой позиции станет не меньше цели или когда закончится массив. В найденном окне запустим бинарный поиск.
Этот способ называют экспоненциальным: расстояния между проверками удваиваются. Время работы при этом не становится экспоненциальным. В нашем примере длина известна и выход за пределы проверяется. Для источника неизвестной длины понадобился бы ещё безопасный способ узнать, что он закончился.
Особенности этого способа
Нужен заранее отсортированный массив. Эта версия возвращает любое точное совпадение в найденном окне. Две фазы могут посетить одну позицию повторно — счётчик учитывает оба посещения.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
После проверки первого элемента идём к позициям 1, 2, 4, 8… и только потом переходим к бинарному поиску.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Если нижняя граница цели находится на позиции p, обе фазы вместе требуют O(log(p + 2)) посещений; в худшем случае — O(log(N + 1)). Вблизи начала это может быть выгодно, а ближе к концу проверок порой больше, чем у обычного бинарного поиска.
Лучший случайO(1)Худший случайO(log(N + 1))Дополнительная памятьO(1)
Попробуйте. Выберите небольшое число в массиве, затем через кнопку «Нет в массиве» — значение больше всех элементов. Найдите шаг, на котором расширение окна сменяется сужением.
Первое значение не меньше искомого
Допустим, награду получают все игроки, набравшие ровно 21 очко. Найти одного уже недостаточно. В упорядоченном списке одинаковые результаты стоят рядом: достаточно определить начало группы и позицию сразу после неё.
Пройдите три задачи по порядку. Сначала найдём левый край, затем правый; вместе они дадут всю группу и её размер. Если искомых очков ни у кого нет, обе границы укажут на одно место для вставки.
Находим место, где заканчиваются значения меньше цели.
Ищем первую позицию, где очков не меньше, чем нужно. Это нижняя граница, или lower bound. При совпадении в середине продолжаем слева: там может стоять ещё один игрок с тем же результатом.
Для очков [10, 20, 20, 40] цель 20 даёт индекс 1. Но для цели 25 ответ тоже существует: индекс 3, перед игроком с 40 очками. Граница показывает место для вставки и сама по себе не подтверждает точное совпадение. Если все результаты меньше цели, вернётся N.
Особенности этого способа
Результат — позиция от 0 до N включительно. Перед чтением values[position] убедитесь, что position < N. Для проверки точного совпадения дополнительно сравните values[position] с целью.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Находим место, где заканчиваются значения меньше цели.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Каждая проверка сокращает окно примерно вдвое. В непустом массиве работа растёт логарифмически независимо от наличия точного совпадения. Найти место для вставки можно за O(log N), а сама вставка в обычный массив может потребовать сдвига O(N) элементов.
Лучший случайO(log N)Худший случайO(log N)Дополнительная памятьO(1)
Попробуйте. Нажимая «Нет в массиве», выберите сначала значение меньше всех элементов, затем больше всех. Ответы 0 и N — полноценные границы, а не ошибки.
Первое значение строго больше
Меняем одно сравнение, чтобы пройти за все равные значения.
Теперь нужен первый игрок, у которого очков строго больше цели. Поэтому равенство обрабатываем иначе: игрок с нужным результатом ещё принадлежит группе, и поиск продолжается справа.
Для очков [10, 20, 20, 40] и цели 20 ответ — индекс 3. Это верхняя граница, или upper bound: позиция после обоих игроков с 20 очками. Она также подходит для вставки нового участника после равных ему по результату.
Особенности этого способа
Ответ N означает, что строго большего элемента нет. Это позиция конца, по которой нельзя читать элемент массива.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Меняем одно сравнение, чтобы пройти за все равные значения.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Окно по-прежнему уменьшается вдвое, поэтому для непустого массива оценка — O(log N). От нижней границы отличается обработка равенства, а не порядок роста работы.
Лучший случайO(log N)Худший случайO(log N)Дополнительная памятьO(1)
Попробуйте. На массиве одинаковых значений сравните нижнюю и верхнюю границы. Проследите, в какую сторону уходит середина при равенстве.
Все совпадающие значения
Две границы описывают всю группу — перебирать её пока не нужно.
Объединяем предыдущие ответы. Игроки с нужными очками занимают [first, afterLast), а размер группы равен afterLast − first. Последний игрок стоит на afterLast − 1, но только если группа не пуста.
Для очков [10, 20, 20, 40] и цели 20 получаем [1, 3): награду нужно выдать двум игрокам. Для цели 25 обе границы равны 3 — подходящих игроков нет. Чтобы выдать награды, найденную группу всё же придётся обойти.
Особенности этого способа
Вспомогательная функция вызывается дважды: при strict = false используется <, при strict = true — <=. Каждый проход начинает со всего массива, как в двух предыдущих примерах.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
Посещено позиций0Ищем очки21
Число в ячейке — очки, подпись снизу — индекс. Иконка обозначает класс персонажа. Ищем по очкам.
По возрастанию очков
Игрок на шаге: —
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Две границы описывают всю группу — перебирать её пока не нужно.
Оценка сложности
Как читать эти оценки
N — длина массива. Оценки относятся к алгоритму со всеми его проходами, но не включают подготовку данных и память для хранения кадров анимации. Пустой массив обрабатывается за постоянное время.
Два логарифмических поиска всё ещё дают O(log N). Для двух границ достаточно O(1) дополнительной памяти. Если затем прочитать или скопировать K найденных элементов, добавится O(K) работы; их подсветка здесь относится к визуализации.
Лучший случайO(log N)Худший случайO(log N)Дополнительная памятьO(1)
Попробуйте. Выберите набор «Все значения равны» и нажмите на любого игрока, затем попробуйте «Нет в массиве». Сопоставьте количество совпадений с количеством посещённых позиций.
Не теряем границы
В примерах с массивом окно [left, right) включает левую границу и исключает правую. Его длина — right − left. Цикл работает только при положительной длине, поэтому середина всегда указывает на существующий элемент.
Исключая середину вместе с левой частью, переходим к mid + 1. Исключая правую часть, устанавливаем right = mid. Каждая итерация без ответа обязана сужать окно. Присваивание left = mid может навсегда оставить окно из одного элемента неизменным.
При поиске нижней границы сохраняются два факта: перед left находятся слишком маленькие значения, а начиная с right — уже подходящие. Когда границы встречаются, место перехода найдено. Им может быть N, хотя элемента values[N] не существует.
В мастерской используется другой договор: обе границы диапазона ответов включены. Там left == right означает, что остался один вариант. Перед переносом кода из другого примера проверьте, как в нём устроены границы.
Минимальный подходящий ответ
Искать можно среди ответов на задачу, даже когда массива с этими ответами нет.
В мастерской четыре отдельных заказа: 3, 6, 7 и 11 деталей. Станок делает rate деталей в час. Каждому заказу отводятся целые часы; остаток последнего часа нельзя передать следующему заказу. Какой минимальной производительности хватит, чтобы уложиться в заданное время?
При производительности 4 нужны 1 + 2 + 2 + 3 = 8 часов. Если станок станет быстрее, времени больше не потребуется. Получается ряд вариантов «слишком медленно», за которым идут только варианты «успеваем». Бинарный поиск находит границу между ними.
Здесь left и right — возможные скорости, причём обе границы включены. Подходящую скорость сохраняем: переносим right на rate. Слишком медленную исключаем: переносим left на rate + 1. Размер самого большого заказа даёт достаточную верхнюю границу, если на каждый заказ разрешён хотя бы один час.
Особенности этого способа
Размеры заказов — положительные целые числа. Четыре непустых заказа требуют хотя бы четырёх часов по условиям задачи, при любой скорости. При меньшем бюджете решения нет. Условие пригодности должно быть монотонным.
Здесь меняется время, отведённое мастерской на четыре заказа. Изменение запускает заново только этот пример. Очки игроков и настройки других примеров остаются прежними.
Деталей в каждом заказе
Проверок условия0Сколько часов есть8
Подбираем минимальное число деталей в час. Сами варианты скорости — числа, не игроки.
Варианты производительности
Окно поиска
Пока не определён
ПроверяемРезультатИсключено
Готовы к первому шагу
Искать можно среди ответов на задачу, даже когда массива с этими ответами нет.
Оценка сложности
Как читать эти оценки
M — число заказов, R — размер самого большого заказа. Время включает поиск максимума и все проверки производительности. Память для хранения кадров анимации в оценку не входит.
Если часов меньше, чем заказов, ответ можно дать сразу за O(1): решения нет. В остальных случаях при M заказах и максимальном размере заказа R одна проверка проходит по M заказам, а проверок требуется O(log R). С учётом поиска максимума и случая с одним вариантом итог — O(M log(R + 1)), дополнительная память — O(1). Быстрый внешний поиск не делает внутреннюю проверку бесплатной.
Лучший случайO(1)Худший случайO(M log(R + 1))Дополнительная памятьO(1)
Попробуйте. Начните с 8 часов: минимальная скорость — 4. Затем попробуйте 4 часа и 3 часа. В последнем случае решения нет, и алгоритм должен честно об этом сообщить.
Как применить поиск
Ускорить поиск можно не только заменой алгоритма. Иногда полезнее подготовить данные один раз, обработать запросы вместе или сохранить уже вычисленное. Разберём эти решения на задачах с игроками.
Стоит ли сортировать ради поиска?
Если в неупорядоченных данных нужно найти одно значение, разумно начать с линейного прохода. Сортировка на сравнениях за O(N log N) и последующий поиск за O(log N) дают большую асимптотическую стоимость, чем один проход за O(N).
Для Q запросов к неизменным данным сравниваем O(QN) и O(N log N + Q log N). Однократная подготовка может окупиться на множестве запросов. Когда это произойдёт по реальному времени, зависит от данных, реализации и оборудования.
Учитывайте и изменения данных. Вставка в упорядоченный массив может сдвинуть множество элементов. Если нужны только точные совпадения и частые изменения, стоит рассмотреть хеш-таблицу; работа с упорядоченными диапазонами предъявляет другие требования.
Сортировка также меняет индексы. Чтобы вернуться к исходной записи, храните вместе со значением её ID или исходный индекс. Позиция в отсортированном представлении сама по себе не указывает на позицию в исходном списке.
Найти всех игроков от 20 до 40 очков
Границы нужны не только для одинаковых значений. Возьмём очки [10, 20, 20, 30, 40, 50] и наградим всех с результатом от 20 до 40 включительно. Нижняя граница для 20 даст индекс 1, верхняя граница для 40 — индекс 5. Нужные игроки занимают [1, 5): это 20, 20, 30 и 40.
Чтобы узнать число награждённых, достаточно вычесть границы: 5 − 1 = 4. Чтобы выдать награды, обойдём только найденную группу. Так одно условие о значениях превращается в небольшой участок массива. Заметьте: 40 входит в условие, но правая граница 5 не входит в диапазон индексов.
Не начинать каждый поиск заново
Допустим, после матча сразу пришли три запроса: есть ли игроки с 20, 25 и 40 очками? Результаты уже упорядочены: [10, 20, 20, 30, 40, 50]. Можно выполнить три бинарных поиска. А если запросов много и их можно обработать вместе, полезен другой приём — два указателя.
Один указатель движется по результатам, другой — по отсортированным запросам. Для 20 пропускаем 10 и находим совпадение. Для 25 продолжаем с прежнего места: проходим обе двадцатки и останавливаемся на 30 — значит, 25 нет. Для 40 идём дальше и находим 40. Ни один указатель не возвращается назад.
Так два упорядоченных списка можно обработать одним совместным проходом. Это полезно для большого пакета запросов; ради одного запроса проходить список заново обычно незачем. Подготовка запросов тоже стоит работы: если меняем их порядок, сохраняем исходные номера, чтобы вернуть ответы на свои места.
Подготовить удобный путь к записи
Поиск игрока по ID и поиск игроков с результатом от 20 до 40 — разные задачи. Для ID можно заранее построить хеш-таблицу «ID → игрок». Для диапазона очков удобно держать отдельный отсортированный список «очки → ID»: он помогает найти нужную группу, не переставляя основной список игроков.
Такой вспомогательный список называют индексом. Он занимает память, а при изменении очков его нужно обновлять. Если признак вычисляется дорого — например, рейтинг получается из истории матчей, — можно сохранить готовые рейтинги и искать по ним. При изменении истории сохранённые значения тоже придётся пересчитать.
Главный вопрос здесь — какая работа повторяется. Один поиск, тысячи запросов к неизменным данным и постоянно меняющийся рейтинг могут требовать разных решений. Сравнивайте весь путь: подготовку, запросы и обновления.
Начните с вопроса
Любое совпадение в упорядоченном массиве
Сравниваем, сужаем окно, завершаемся при совпадении.
Сначала пропустить блоки, затем проверить один
Два этапа на упорядоченных данных. Полезный пример сочетания приёмов; не замена бинарному поиску по умолчанию.
Искомое предположительно близко к началу
Сначала определяем окно; дополнительные проверки не всегда выгодны.
Первое значение ≥ цели; вставка перед равными
Ответом может быть N. Проверяем границу перед чтением.
Первое значение > цели; вставка после равных
Равенство относится к исключаемой левой части.
Количество или границы равных значений
Находим две границы; перебираем диапазон только при необходимости.
Минимальный ответ с монотонным условием
В оценку сложности включаем стоимость проверки условия.
Сравниваем работу, а не только ответы
Смените набор или искомое значение через «Общий массив» прямо здесь — все строки с игроками пересчитаются. Таблица показывает итог полного поиска, независимо от шага, на котором остановлена анимация. За одно посещение считаем одну проверку выбранной позиции, даже если её значение участвует в нескольких сравнениях. Возврат к той же позиции считается ещё раз. Это не число уникальных элементов, не подсчёт всех операций и не измерение времени. Для мастерской отдельно считаются полные проверки условия; её время можно изменить под таблицей.
Этот массив общий для всех примеров с игроками. Изменение данных возвращает их к первому шагу.
Нажмите на игрока, чтобы искать его очки. Все игроки с таким же результатом выделятся вместе.
Искомое значение:
Эта кнопка выбирает отсутствующее значение. Повторное нажатие — другой вариант.
| Способ | Посещено позиций / проверок условия | Результат |
|---|---|---|
| Линейный | — | — |
| Бинарный | — | — |
| Прыжки и перебор | — | — |
| Поиск с удвоением | — | — |
| Нижняя граница | — | — |
| Верхняя граница | — | — |
| Диапазон совпадений | — | — |
| Бинарный поиск по ответу | — | — |
Линейный поиск видит исходный порядок, остальные примеры с массивом — отсортированную копию. Её подготовка в счётчики не входит. Точное совпадение, граница и диапазон отвечают на разные вопросы: их результаты нельзя подменять друг другом.
Здесь меняется время, отведённое мастерской на четыре заказа. Изменение запускает заново только этот пример. Очки игроков и настройки других примеров остаются прежними.
Деталей в каждом заказе
Попробуйте до просмотра разбора
Ищем 15 в [5, 10, 20, 30]. Когда последовательный поиск может остановиться раньше конца?
Разбор
Когда встретит 20 — но только если известно, что массив отсортирован, и в алгоритме есть проверка «текущее значение больше цели». Обычный поиск только по равенству продолжит проход. Без сортировки после 20 вполне могло бы стоять 15.
На краю блока стоят 30 очков, а мы ищем 20. Можно ли пропустить весь блок?
Разбор
Нет. Мы знаем только, что остальные значения в упорядоченном блоке не больше 30; среди них могут быть 20. Пропускать блок целиком можно, когда даже его последнее значение меньше цели. Иначе переходим к перебору внутри блока.
Что вернут две границы для цели 4 в массиве [2, 4, 4, 4, 9]?
Разбор
Нижняя граница — 1, верхняя — 4. В диапазоне [1, 4) три совпадения. Обычный бинарный поиск вправе вернуть индекс 1, 2 или 3.
Куда вставить 6 в массив [2, 4, 4, 9]? Значит ли это, что мы нашли 6?
Разбор
Обе границы равны 3. Это место для вставки перед 9. Точного совпадения нет: по индексу 3 находится 9, а не 6.
Что должно происходить с пустым массивом?
Разбор
Точный поиск возвращает notFound, не читая ни одного элемента. Обе границы равны 0, диапазон совпадений — [0, 0). Место для вставки существует даже без элементов.
Можно ли применить наш бинарный поиск к [2, 9, 4, 7] без подготовки?
Разбор
Нет: используемое правило требует упорядоченности. Значение в середине не позволяет надёжно выбрать половину. Можно отсортировать копию или воспользоваться линейным поиском.
Почему мастерская не успеет сделать заказы на 3, 6, 7 и 11 деталей за 8 часов при скорости 3?
Разбор
Потребуется ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10 часов. При скорости 4 хватит восьми, поэтому 4 — первая подходящая скорость.