Estou com dúvidas em relação a busca sequêncial e binária no c++

[Visitante]

Olá, estou com algumas dúvidas em alguns exercícios dessa listinha:

https://uploaddeimagens.com.br/imagens/2-jpg--1500

 

Nessa letra b da primeira questão, pelo q eu vi dessa menina fazendo, eu entendi q as comparações eram feitas em cada if ou else contando sempre os dois!!!! E só deu esse resultado quando eu coloquei aqueles conts no código da função q está na letra c!!!! Tente ver o meu raciocínio na letra b. Na letra d eu coloquei uma justificativa n muito confiável rsrsrsrsrsrs e mudei a função para receber um vetor d chars, alguém poderia analisar pra ver se ta certo rsrsrsrsrs

 

1)

a)      Essa função faz uma busca binária.

      a[10]={'b','d','g','i','i','o','o','r','r','r'}; //Esta é a ordenação do nome rodrigorib !

 

esq=0;                                                                                                                              

dir=9;

 

i=(esq+dir)/2

x<a

x>a

 

i=(0+9)/2=4.5                                                                                                                                

 

‘d’ < a[4] -> true  --> 1 comparação                                                                             esq=0                                                 

‘d’ > a[4] -> false --> 1 comparação                                                                             dir=4-1=3

 

i=(0+3)/2=1.5

 

‘d’ < a[1] -> false --> 1 comparação

‘d’ > a[1] -> false --> 1 comparação

 

1+1+1+1=4

 

Letra encontrada! Foram feitas 4 comparações.

 

c)       int processa(char a[], int n, char x){

  int esq=0;

           int dir = n-1;

           int i;

           int cont=0;

        while (esq<=dir){

        i = (dir+esq)/2;

        cont++;

        if(x<a){

            dir=i-1;

            cont++;

        }

        else if (x>a){

            esq=i+1;

            cont++;

        }

        else{

            cont++;

            return cont;

        }

    }

    return -1;

}

d)      int processa2(char a[], int n, char x){

    int cont=0;

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

        cont++;

        if (x==a){

        return cont;

        }

    }

    return -1;

}

 

 

 

a==x -> false

1.  

a==x ->true

 

Foram feitas 2 comparações! No caso da função processa2, que consiste no método da busca sequencial, ela fez menos comparações que a função de busca binária que é a processa, então nesse caso ela foi mais eficaz, porém a busca binária é mais eficiente em vetores maiores, fazendo bem menos comparações.

[Ansi C]

É interessante mencionar também que a busca binaria também depende da indexação dos dados.

E contra posto a sequencial não necessita desse recurso.

Ao acaso pode bem chegar ao x da questão com um pouco de sorte, bem mais rápido.