Binary Search

Лёгкая№704найти число

Дан массив различных чисел, отсортированный по возрастанию, и искомое число. Нужно вернуть индекс этого числа или −1, если его в массиве нет, причём за O(log n). Наш пример: [-4, 0, 3, 9, 14, 20, 27] и 15 — ответ −1: место 15 между 14 и 20, но его там нет.

704 Binary SearchРазбор · 1×

Пример: [-4, 0, 3, 9, 14, 20, 27], ищем 15. Бледные числа отброшены: искомого среди них быть не может.

0-4102339414520627lo
ещё в диапазонесередина, проверяемотброшено

lo — первый индекс, 0

01/19
сначала · назад · пуск · шаг
Скорость
1function search(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi: // one number left still counts
5 mid = floor((lo + hi) / 2)
6 if nums[mid] == target:
7 return mid
8 if nums[mid] < target:
9 lo = mid + 1
10 else:
11 hi = mid - 1
12 return -1
состояние
lo
0
hi
–
mid
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Массив отсортирован, поэтому одно сравнение с серединой показывает, в какой половине может быть искомое. Другая половина отбрасывается целиком.
  2. lo сдвигается только правее mid, а hi — только левее, поэтому диапазон сужается на каждом шаге и цикл всегда заканчивается.
  3. Цикл идёт, пока lo <= hi, поэтому диапазон из одного числа тоже проверяется. Когда lo обогнал hi, места для искомого не осталось: его в массиве нет.

Сложность

Время O(log n): каждый шаг делит диапазон пополам, поэтому на 7 чисел хватает 3 проверок. Память O(1): три индекса.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.