Ctrl K

Поиск в упорядоченном списке

Лёгкая
В архиве хранится список номеров ids, отсортированный по возрастанию; все номера разные. Нужно узнать, где в нём лежит номер wanted. Верните индекс wanted в ids (нумерация с нуля) или -1, если такого номера нет. Просмотреть весь список подряд — слишком долго: решение должно работать за O(log n).
Пример 1
ids=[-7, 2, 15, 40, 41, 300], wanted=40 → 3

Номер 40 стоит на позиции 3.

Пример 2
ids=[-7, 2, 15, 40, 41, 300], wanted=16 → -1

Номера 16 в списке нет, поэтому -1.

Пример 3
ids=[5], wanted=5 → 0
Ограничения
  • 1 ≤ len(ids) ≤ 10⁴
  • -10⁴ ≤ ids[i], wanted ≤ 10⁴
  • Все ids[i] различны, список строго возрастает
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиМесто на отсортированной полке ЛёгкаяПотерянный билет ЛёгкаяЗначения в обоих списках ЛёгкаяОбщие значения с повторами ЛёгкаяСледующая буква по кругу Лёгкая
загружаем Python…
Вход
ids=[-7, 2, 15, 40, 41, 300], wanted=40
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 111 тестов на сервере, включая скрытые.