Рекурсивный двоичный поиск
Иногда бывает очень удобно реализовать двоичный поиск рекурсивно. Вам нужно написать функцию двоичного поиска, которая возвращает индекс самого левого элемента
target в массиве, если такой элемент найден, или -1 в противном случае.Входные данные
Первая строка содержит два целых числа
n (1 ≤ n ≤ ) — количество элементов, и q (1 ≤ q ≤ ) — количество запросов.Следующая строка содержит
n целых чисел, разделенных пробелами: ( ≤ ≤ ), расположенных в порядке возрастания.Последняя строка содержит
q целых чисел, разделенных пробелами: ( ≤ ≤ ), которые являются искомыми значениями.Выходные данные
Программа должна вывести
q чисел, каждое из которых соответствует результату поиска для соответствующего значения (индексация начинается с 0).Примеры
Входные данные | Выходные данные |
9 3
20 22 23 23 34 49 52 55 58
49 22 24 | 5 1 -1 |
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB