Busca Binária

// BUSCA BINÁRIA
// Complexidade:
// • Ordenação: O(NlogN)
// • Busca: O(logN)


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, q;
    while(cin >> n >> q)
    {
        int v[n];
        for(int i = 0; i < n; i++)
            cin >> v[i];

        sort(v, v + n); //O(n*logn): ordenar o vetor

        //O(q*logn)
        while(q--) //O(q): cada valor que eu quero procurar
        {
            int busca; //numero que eu quero procurar no vetor
            cin >> busca;

            int baixo = 0; //limite inferior
            int alto = n - 1; //limite superior
            bool achei = false;
            while(!achei && baixo <= alto) //O(logn): busca binária
            {
                int meio = (alto + baixo) / 2;

                if(v[meio] == busca) //achei o elemento no vetor
                    achei = true;

                else if(v[meio] < busca) //se é menor, aumento o limite inferior
                    baixo = meio + 1;

                else //se é maior, diminuo o limite superior
                    alto = meio - 1;
            }

            if(!achei) cout << busca << " nao existe no vetor" << endl;
            else cout << busca << " existe no vetor" << endl;
        }

        //O((n+q)*logn): complexidade total
        //A busca binária também pode retornar a posição do vetor em que o elemento foi encontrado
    }
    return 0;
}