TOPIC

Busca binária não passa? (TLE)

Daniel Mendes asked 1 year ago

Há algo errado? Usar ponteiro resolveria?

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

int b_search(vector <int> lista, int l_esquerdo, int l_direito, int numero_procurado){

    if(l_direito>=l_esquerdo){

        int meio=l_esquerdo+(l_direito-l_esquerdo)/2;

        if(lista[meio]==numero_procurado) return meio; //posição do n procurado;

        if(lista[meio]>numero_procurado) return b_search(lista, l_esquerdo, meio-1, numero_procurado);

        return b_search(lista, meio+1, l_direito, numero_procurado);

    }

    return -1; //não foi encontrado

}

int main(){

    int n, q, q_tmp, tmp, caso=1;
    vector <int> marbles;

    //freopen("input.txt", "r", stdin);

    cin>>n>>q;
    do{

        cout<<"CASE# "<<caso<<":"<<endl;

        for(int i=0;i<n;i++){
            cin>>tmp;
            marbles.push_back(tmp);
        }

        sort(marbles.begin(), marbles.end());

        for(int i=0;i<q;i++){

            cin>>q_tmp;

            //lista - limite esquerdo - limite direito - número procurado;
            tmp=b_search(marbles, 0, marbles.size()-1, q_tmp);

            if(tmp==-1) cout<<q_tmp<<" not found"<<endl;
            else cout<<q_tmp<<" found at "<<tmp+1<<endl;

        }

        marbles.clear();
        cin>>n>>q;
        caso++;

    }while(n!=0&&q!=0);

    return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • feodorv replied 1 year ago

    Is it correct problem for your code?