Поиск в отсортированном массиве

Просмотр в формате PDF

Submit solution


Очки: 110
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Problem types
Allowed languages
C++, Python

Оператор работает с журналом записей, упорядоченным по возрастанию ключей. Все ключи в журнале различны.

По заданному ключу q нужно определить номер записи, в которой он находится. Если записи с таким ключом в журнале нет, необходимо вывести -1.

Нумерация записей ведётся с единицы.

Входные данные

В первой строке даны числа n и q (1 <= n <= 2 * 10^5, |q| <= 10^9) — количество записей в журнале и ключ, который нужно найти.

Во второй строке даны n различных целых чисел в порядке возрастания — ключи записей журнала (|a_i| <= 10^9).

Выходные данные

Выведите индекс записи с ключом q, если такая запись существует, иначе выведите -1.

Ограничения

  • 1 <= n <= 2 * 10^5
  • |q| <= 10^9
  • |a_i| <= 10^9
  • Все ключи различны
  • Ключи во входном журнале отсортированы по возрастанию

Примеры

Пример 1

Входные данные

1 5
5

Выходные данные

1
Пример 2

Входные данные

2 -7
-7 0

Выходные данные

1

Комментарии

Еще нет ни одного комментария.