Binary Search

Q: Какова временная сложность бинарного поиска?

O(log n) . Каждое сравнение вдвое уменьшает диапазон, в котором ещё может находиться цель, поэтому после k шагов остаётся не более n / 2^k кандидатов. Для списка из 10^4 элементов требуется не более 14 сравнений, а для списка из 10^9 элементов — не более 30. Итеративный вариант использует дополнительную память объёмом O(1) .

Q: Почему для бинарного поиска нужен отсортированный массив?

Шаг, на котором отбрасывается половина списка, зависит от порядка элементов. Когда nums[mid] < target , сортировка гарантирует, что каждый элемент слева от mid тоже меньше, чем target , поэтому ни один из них не может совпасть. В неотсортированном списке это сравнение ничего не говорит об остальных элементах, поэтому нужно проверить их все.

Q: Должен ли бинарный поиск быть итеративным или рекурсивным?

Оба варианта правильные, и оба работают за время O(log n) . Рекурсивный вариант вызывает сам себя для одной из половин и использует O(log n) памяти стека; итеративный вариант перемещает lo и hi в цикле и использует O(1) . На собеседованиях обычно ожидают цикл, и он позволяет избежать ограничений на глубину рекурсии.

Q: Как избежать переполнения при вычислении среднего индекса?

Пишите mid = lo + (hi - lo) / 2 вместо (lo + hi) / 2 . Оба варианта дают один и тот же индекс, но во втором сначала складываются два индекса, и для 32-битного целого числа эта сумма переполняется, когда значения индексов превышают примерно 1.07 × 10^9 . В Python и Ruby целые числа не ограничены по размеру, поэтому там короткая форма безопасна.

ЛегкоБинарный поиск

+10

Дан список целых чисел nums, отсортированный по возрастанию, без повторяющихся значений, и целое число target. Верните индекс target в nums, считая с 0, или -1, если его нет в списке. Стремитесь к времени выполнения O(log n), то есть вы не можете позволить себе проверять каждый элемент.

Функция

search(nums: integer-array, target: integer) → integer

numsinteger-array: отсортированный список различных целых чисел
targetinteger: значение, которое нужно найти
Возвращаетinteger: индекс target в nums или -1, если он отсутствует

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
Массив nums отсортирован в строго возрастающем порядке, поэтому каждое значение встречается один раз.

Примеры

Ввод: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Вывод: 4
Пояснение: nums[4] равно 9. Поиск проверяет индекс 3 (значение 4, слишком маленькое), затем индекс 5 (значение 15, слишком большое), а потом индекс 4, где находит 9.

Ввод: nums = [1, 3, 5, 8, 13, 21]target = 10
Вывод: -1
Пояснение: 10 находилось бы между 8 и 13, и ни одно из этих чисел не равно 10, поэтому его нет в списке. Диапазон поиска сужается, пока lo не станет больше hi, и функция возвращает -1.

+15 скрытых тестов при отправке

Дополнительный вопрос

Если значения в nums могут повторяться, как вернуть первый индекс target, по-прежнему за O(log n)?

Подсказки

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

Открыто 0 из 3

Решение

Последовательный просмотр элементов находит target, но игнорирует тот факт, который делает задачу интересной: список отсортирован. Одно сравнение со средним элементом показывает, в какой половине ещё может находиться target, поэтому на каждом шаге можно отбросить половину вариантов. Для списка из 10^4 элементов тогда потребуется не более 14 сравнений вместо 10000.

Сканируйте слева направо

Идея

Проверяйте каждый индекс по порядку и возвращайте первый, значение по которому равно target. Если цикл завершится без совпадения, значит, target нет в списке, поэтому верните -1. Каждый элемент сравнивается один раз, поэтому ответ будет правильным для любого списка — отсортированного или нет.

Проблема в такой универсальности. Для списка из 10^4 элементов может потребоваться до 10000 сравнений, а объём работы растёт пропорционально n. При сканировании не используется тот факт, что nums отсортирован, поэтому не достигается оценка O(log n), требуемая задачей. Можно остановиться, как только значение станет больше target, но в худшем случае всё равно придётся просмотреть весь список.

Алгоритм

Для каждого индекса i от 0 до n-1 сравните nums[i] с target.
Если они равны, верните i.
После цикла верните -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Бинарный поиск с двумя индексами

Идея

Храните два индекса, lo и hi, и соблюдайте одно условие: если target есть в списке, его индекс находится между lo и hi включительно. В начале этот диапазон охватывает весь список — от 0 до n-1. Посмотрите на средний индекс mid. Если nums[mid] равен target, задача решена. Если он меньше, то, поскольку список отсортирован, все элементы до mid тоже меньше, поэтому переместите lo на mid + 1. Если он больше, переместите hi на mid - 1. После любого из этих перемещений условие по-прежнему выполняется.

Проследите за первым примером: [-7, -2, 0, 4, 9, 15, 23] с target = 9. Диапазон от 0 до 6 имеет середину 3, значение 4 — слишком маленькое, поэтому диапазон становится от 4 до 6. В его середине, 5, находится 15 — слишком большое значение, поэтому диапазон становится от 4 до 4. В индексе 4 находится 9: верните 4.

Если target отсутствует, диапазон продолжает сужаться, пока lo не станет больше hi. Тогда диапазон пуст, условие говорит, что target нигде нет, и вы возвращаете -1. На каждом шаге диапазон уменьшается вдвое, поэтому цикл выполняется не более примерно log2(n) + 1 раз: 14 шагов для 10^4 элементов. Для этого достаточно двух индексов — это вся дополнительная память, которая вам нужна.

Алгоритм

Установи lo = 0 и hi = n-1.
Пока lo ≤ hi, вычисли mid = lo + (hi - lo) / 2.
Если nums[mid] равно target, верни mid.
Если nums[mid] < target, установи lo = mid + 1; иначе установи hi = mid - 1.
Когда цикл завершится, верни -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Ловушки и крайние случаи

Бинарный поиск короткий, и почти все ошибки — это ошибки на единицу на границах диапазона.

Цикл с условием lo < hi, когда hi изначально равен последнему индексу. Цикл завершается, пока один из кандидатов ещё не проверен, поэтому при nums = [5] и target = 5 возвращается -1. Для включительного диапазона используйте цикл с условием lo ≤ hi.
Присваивание lo = mid или hi = mid для включительного диапазона. Когда lo и hi соседние, mid равен lo, и диапазон не сужается: цикл становится бесконечным. Вы уже проверили nums[mid], поэтому шагайте за него, используя mid + 1 или mid - 1.
Вычисление (lo + hi) / 2 с целым числом фиксированной разрядности. Сумма переполняется, когда индексы превышают примерно 10^9. Здесь пределы намного ниже, но безопаснее привыкнуть использовать lo + (hi - lo) / 2.
Возврат lo, если target отсутствует. После завершения цикла lo — это точка вставки, которая является допустимым индексом, а не -1.
Забыть о сдвиге в Lua и R. Их списки начинаются с 1, поэтому возвращаемый индекс — это позиция минус 1.

Частые вопросы4

Какова временная сложность бинарного поиска?

O(log n). Каждое сравнение вдвое уменьшает диапазон, в котором ещё может находиться цель, поэтому после k шагов остаётся не более n / 2^k кандидатов. Для списка из 10^4 элементов требуется не более 14 сравнений, а для списка из 10^9 элементов — не более 30. Итеративный вариант использует дополнительную память объёмом O(1).

Почему для бинарного поиска нужен отсортированный массив?

Шаг, на котором отбрасывается половина списка, зависит от порядка элементов. Когда nums[mid] < target, сортировка гарантирует, что каждый элемент слева от mid тоже меньше, чем target, поэтому ни один из них не может совпасть. В неотсортированном списке это сравнение ничего не говорит об остальных элементах, поэтому нужно проверить их все.

Должен ли бинарный поиск быть итеративным или рекурсивным?

Оба варианта правильные, и оба работают за время O(log n). Рекурсивный вариант вызывает сам себя для одной из половин и использует O(log n) памяти стека; итеративный вариант перемещает lo и hi в цикле и использует O(1). На собеседованиях обычно ожидают цикл, и он позволяет избежать ограничений на глубину рекурсии.

Как избежать переполнения при вычислении среднего индекса?

Пишите mid = lo + (hi - lo) / 2 вместо (lo + hi) / 2. Оба варианта дают один и тот же индекс, но во втором сначала складываются два индекса, и для 32-битного целого числа эта сумма переполняется, когда значения индексов превышают примерно 1.07 × 10^9. В Python и Ruby целые числа не ограничены по размеру, поэтому там короткая форма безопасна.

Python

def search(nums, target):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Ожидается