Busca_binaria_em_O(Q*log₂ N).cpp

#include <bits/stdc++.h>
  
using namespace std;
  
int N, Q, VETOR[100050], X;

int main()
{
    cin >> N >> Q;
  
    for(int i = 1; i <= N; i++) cin >> VETOR[i];
  
    for(int i = 1; i <= Q; i++)
    {
        cin >> X;
  
        int ini = 1, fim = N, meio;
  
        bool achou = false;
  
        while(fim >= ini)
        {
            meio = (ini + fim)/2;
  
            if(X < VETOR[meio]) fim = meio - 1;
  
            if(X > VETOR[meio]) ini = meio + 1;
  
            if(X == VETOR[meio])
            {
                achou = true;
  
                break;
            }
        }
  
        if(achou) cout << "S\n";
  
        else cout << "N\n";
    }
     
    return 0;
}