Маяк 1. Пропавшая радиограмма
Экспедиция «МАЯК». Диспетчер получил запрос на радиограмму с кодом x. Все радиограммы хранятся в архиве по возрастанию кода, и двух сообщений с одинаковым кодом не бывает. Диспетчеру нужен номер ячейки, в которой хранится нужная радиограмма. Если такой радиограммы никогда не поступало, нужно сообщить об этом.
Входные данные
В первой строке записаны целые числа n и x — количество радиограмм и код запроса. Во второй строке — n различных кодов, расположенных в строго возрастающем порядке.
Выходные данные
Выведите номер ячейки с кодом x (нумерация с 0). Если радиограммы нет, выведите -1.
Ограничения
0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения строго возрастают. При n = 0 вторая строка пустая.
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| № | Входные данные | Выходные данные |
|
1
|
7 19
3 8 12 19 24 31 46
|
3
|
|
2
|
7 14
3 8 12 19 24 31 46
|
-1
|