Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Busca Binária

a guest Apr 3rd, 2020 238 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. // BUSCA BINÁRIA
  3. // Complexidade:
  4. // • Ordenação: O(NlogN)
  5. // • Busca: O(logN)
  6.  
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10.  
  11. int main()
  12. {
  13.     int n, q;
  14.     while(cin >> n >> q)
  15.     {
  16.         int v[n];
  17.         for(int i = 0; i < n; i++)
  18.             cin >> v[i];
  19.  
  20.         sort(v, v + n); //O(n*logn): ordenar o vetor
  21.  
  22.         //O(q*logn)
  23.         while(q--) //O(q): cada valor que eu quero procurar
  24.         {
  25.             int busca; //numero que eu quero procurar no vetor
  26.             cin >> busca;
  27.            
  28.             int baixo = 0; //limite inferior
  29.             int alto = n - 1; //limite superior
  30.             bool achei = false;
  31.             while(!achei && baixo <= alto) //O(logn): busca binária
  32.             {
  33.                 int meio = (alto + baixo) / 2;
  34.  
  35.                 if(v[meio] == busca) //achei o elemento no vetor
  36.                     achei = true;
  37.                
  38.                 else if(v[meio] < busca) //se é menor, aumento o limite inferior
  39.                     baixo = meio + 1;
  40.                
  41.                 else //se é maior, diminuo o limite superior
  42.                     alto = meio - 1;
  43.             }
  44.            
  45.             if(!achei) cout << busca << " nao existe no vetor" << endl;
  46.             else cout << busca << " existe no vetor" << endl;
  47.         }
  48.    
  49.         //O((n+q)*logn): complexidade total
  50.         //A busca binária também pode retornar a posição do vetor em que o elemento foi encontrado
  51.     }
  52.     return 0;
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top