Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Бинарный поиск в массиве

Условие задачи  
ID 33591: Количество чисел, равное искомому
Количество чисел, равное искомому
Темы: Бинарный поиск в массиве   

Требуется определить в заданном массиве количество элементов, равных искомому числу.

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

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше предыдущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

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

Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.

Если в массиве нет такого числа, выведите 0.

Примеры
Входные данные Выходные данные
1 4
1 2 2 4
4
1 4 3 2
1
1
0
2

ID 25959: Двоичный поиск
Двоичный поиск
Темы: Бинарный поиск в массиве   

Реализуйте алгоритм бинарного поиска.
 
Входные данные: 
- в первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\));
- во второй строке задаются N элементов первого массива, отсортированного по возрастанию; 
- в третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).
 
Выходные данные: требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.
 
Примеры
Входные данные Выходные данные
1
10 5
1 2 3 4 5 6 7 8 9 10 
-2 0 4 9 12
NO
NO
YES
YES
NO

ID 25960: Левый и правый двоичный поиск
Левый и правый двоичный поиск
Темы: Бинарный поиск в массиве   

Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.
 
Входные данные:
- в первой строке входных данных записано два числа 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