Вопрос по информатике:
На с++
Реализуйте алгоритм бинарного поиска.
Входные данные
В первой строке входных данных содержатся натуральные числа N и K (0NK100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109
Выходные данные
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.
Примеры
входные данные
10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
выходные данные
NO
NO
YES
YES
NO
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 21.10.2017 14:59
- Информатика
- remove_red_eye 14347
- thumb_up 13
Ответы и объяснения 1
#include
#include
using namespace std;
template
bool bin_s(const Iter begin, const Iter end, const T& val)
{
Iter i = std::lower_bound(begin, end, val);
if (i != end && !(val < *i))
return true;
else
return false;
}
int main()
{
size_t N, M;
cin >> N >> M;
vector v1(N);
vector v2(M);
for (size_t i = 0; i < N; ++i)
cin >> v1[i];
for (size_t i = 0; i < M; ++i)
{
cin >> v2[i];
if ( bin_s(v1.begin(), v1.end(), v2[i]) )
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
- 22.10.2017 02:58
- thumb_up 2
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.