Question

На с++
Реализуйте алгоритм бинарного поиска.

Входные данные
В первой строке входных данных содержатся натуральные числа 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

Answer 1

//g++  5.4.0

#include <iostream>
#include <vector>
using namespace std;

template<class Iter, class T>
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<int> v1(N);
    vector<int> 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;
    }
}