Где применяется
1. Задача
Префиксные суммы опирались на то, что данные лежат подряд: поэтому можно было сложить любой отрезок. У отсортированных данных есть другое полезное свойство: порядок. Если список упорядочен, чтобы найти один элемент, не нужно смотреть на все. Одна проверка отбрасывает половину списка.
У тебя миллион строк лога, записанных по порядку времени. Тебя просят найти запись за 14:32:07. Можно читать сверху, строку за строкой, пока не наткнёшься на нужную. На миллионе строк это до миллиона чтений на один поиск, а искать приходится постоянно.
Если данные уже отсортированы, любой элемент из миллиона находится примерно за 20 проверок, а не за миллион.
2. Простыми словами
Возьми отсортированный тестовый список [1, 3, 5, 7, 9, 11] и ищи 7. Посмотри на число посередине: 5. Оно меньше 7. Список отсортирован, поэтому 1 и 3, которые стоят левее 5, ещё меньше. Один взгляд убрал три числа. Остались 7, 9 и 11. Посмотри на их середину: 9. Это больше 7, значит, 9 и 11 отпадают. Осталось только 7, и это искомое число. Три взгляда вместо шести.
Чем длиннее список, тем больше выигрыш. Каждый взгляд убирает примерно половину того, что осталось. Миллион отсортированных строк лога сжимается до 500 000, потом до 250 000, потом до 125 000 и так далее. После 19 взглядов остаётся одна строка, и 20-й взгляд проверяет её. Это работает только потому, что список упорядочен. В неупорядоченном списке то, что 5 меньше 7, ничего не говорило бы о соседях пятёрки.
3. Идея
Заведи две метки, lo и hi. Они ограничивают часть массива, где ещё может быть искомое значение. В начале это весь массив. Смотри на элемент посередине между ними.
Исходов три. Если средний элемент равен искомому, поиск закончен. Если он меньше искомого, искомое может быть только правее, поэтому сдвинь lo за середину. Если он больше, искомое левее, поэтому сдвинь hi перед серединой. Каждая проверка отбрасывает половину того, что осталось.
Одно правило защищает от бесконечного цикла: ставь lo на mid + 1, а hi на mid - 1, и никогда не ставь их на сам mid. Если метка снова встанет на mid, диапазон перестанет сужаться, и цикл будет крутиться вечно. Останавливайся, когда lo станет больше hi. Это значит, что искомого значения в массиве нет, и нужно вернуть -1.
Проследим на [1, 3, 5, 7, 9, 11], ищем 7.
- Начало:
lo = 0,hi = 5. Середина на индексе 2, там 5. Это меньше 7, поэтомуlo = 3. - Теперь
lo = 3,hi = 5. Середина на индексе 4, там 9. Это больше 7, поэтомуhi = 3. - Теперь
lo = 3,hi = 3. Середина на индексе 3, там 7. Совпало.
Найдено на индексе 3: три проверки вместо шести.
4. Во что это обходится
Время O(log n): каждый шаг делит остаток пополам. Миллиону элементов нужно примерно 20 шагов, миллиарду примерно 30. Это та самая почти горизонтальная кривая из урока 09: с ростом данных она почти не растёт.
Память O(1): три переменные-индекса, и ничего, что росло бы вместе с массивом. Условие одно: вход должен быть уже отсортирован. Если он не отсортирован, сортировка стоит O(n log n). Она окупается, только если поисков будет много.
5. Где это встречается
Поиск записи в отсортированных логах и хранилищах временных рядов. Поиск по B-дереву (структуре, на которой построены индексы баз данных) это бинарный поиск, приспособленный к работе с диском. Поиск версии в отсортированном списке релизов. Функции lower_bound и upper_bound в стандартных библиотеках. Команда git bisect ищет коммит, в котором появился баг: она каждый раз делит диапазон коммитов пополам. Это та же идея, только по истории версий, а не по массиву.
binarySearch([1, 3, 5, 7, 9, 11, 13, 15], 13)lo
hi
Ищем 13 в отсортированном массиве. lo и hi отмечают отрезок, где оно ещё может быть: сначала это весь массив.
Столбики: отсортированные числа. Бинарный поиск делит диапазон пополам при каждом сравнении, линейный просмотр читает их по одному.
Одна операция: одно сравнение с искомым числом. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n)O(log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- отсортированный массив
- найти цель / первое или последнее вхождение
- n до 1e6+ и ожидается O(log n)
- найти границу, где условие меняется
- поиск во вращённом, но почти отсортированном массиве (с подвохом)
Похоже, но не то
- Линейный поиск (Linear search)
Перебор читает каждый элемент, но порядка не требует. Бинарному поиску порядок нужен, зато он читает log n.
- Бинарный поиск во вращённом массиве (Binary search on a rotated array)
Поворот рвёт единый отсортированный кусок. Проверка сначала ищет отсортированную половину.
- Бинарный поиск по ответу (Binary search on the answer)
Там отрезок это множество возможных ответов, а не массив. Проверку вы пишете сами.
- Двоичное дерево поиска (Binary search tree)
Дерево делит пополам так же, но через указатели. Ещё оно допускает вставки, чего массив не умеет.
- Два указателя (с концов) (Two pointers (opposite ends))
Там двигаются оба конца, и проверяемая пара меняется. Здесь за шаг двигается одна граница.
n до 1e9 нормально, потому что log2 от 1e9 около 30. Время O(log n), память O(1).
На LeetCode
Задачи, где значение ищут в отсортированных данных за O(log n), включая загаданное число, о котором можно только спрашивать, и сетку, отсортированную строка за строкой. Дели диапазон пополам при каждой проверке.
Это задача урока, от lo <= hi до -1 в конце.
Вместо чтения массива середину проверяет вызов guess(mid).
Ищи бинарным поиском среди чисел от 1 до num такое, чей квадрат ровно num.
Считай сетку одним отсортированным списком, где позиции p соответствуют строка p / n с округлением вниз и столбец p % n.
Твоя задача (Tier 1)
Напиши функцию binarySearch(nums, target).
Список отсортирован от меньшего к большему. Смотри на число посередине, потом отбрасывай половину, где target быть не может. Повторяй, пока не найдёшь его или пока числа не кончатся. Верни позицию target или -1, если его нет.
- Вход:
nums, список чисел по возрастанию, иtarget, число, которое ищешь. Пример:[1, 3, 5, 7, 9, 11], target7. - Возвращает: позицию
targetили-1, если его нет.
Шаги:
- Задай
lo = 0(первая позиция), аhiпоставь на последнюю позицию. - Пока
lo <= hi, бери среднюю позициюmid. Еслиnums[mid]равноtarget, верниmid. Еслиnums[mid]меньшеtarget, ищи в правой половине (lo = mid + 1). Если больше, ищи в левой (hi = mid - 1). - Если диапазон опустел, а совпадения не было, верни
-1.
Готово, когда проходят все тесты:
[1, 3, 5, 7, 9, 11], target7->3[1, 2, 3], target1->0(первое число)[1, 2, 3], target3->2(последнее число)[1, 2, 3], target4->-1(больше всех чисел)[2, 4], target1->-1(меньше всех чисел)[], target5->-1(пустой список, функция не должна падать)[5], target5->0(одно число)
Практика
binarySearch
binarySearch(nums, target) -> index (0-based) or -1
export function binarySearch(nums, target) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.