Левый и правый двоичный поиск
Задача
Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.
Входные данные:
- в первой строке входных данных записано два числа N и M (\(1<=N,\ M <=20000\));
- во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка;
- в третьей строке записаны M целых неотрицательных чисел - элементы второго списка.
Все числа в списках - целые 32-битные знаковые.
Выходные данные: программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
|
10 10
3 4
7 7
1 2
0
|