C Busca binária interativa:Não acontece nada quando busco um valor dentro do vetor

[rafael_carmo]

Meu código:

 

Eu usei busca binária interativa para encontrar um valor n dentro do meu vetor[10]

 

#include <stdio.h> // Funções de entrada e saída
#include <stdlib.h> // Função padrão
#include <locale.h> // Habilita o uso de acentuação em palavras

// Adicionar novas bibliotecas acima de acordo com necessidade 

/*
    // Espaço destinado a transcrição do enunciado para não ficar olhando toda hora a lista

    Escreva um programa que leia um vetor de 10 posições ordenados de inteiros e um
inteiro. O programa deve informar a primeira posição onde este inteiro ocorre no vetor ou
-1 caso o valor não ocorra no vetor (Busca Binária).

*/

    int buscabinariainterativa(int *vetor,int chave,int fim){
        int inicio = 0;
        int meio = (inicio + fim)/2;

        while(inicio<=fim){

            if(chave == vetor[meio]){

                return meio;

            }else{

                if(chave < vetor[meio]){

                    fim = meio - 1;

                }else{
                    
                    inicio = meio + 1;
                }
            }

        }

        return -1;
    }

int main() // Função obrigatória
   {
	/* Declaração de constantes ou variáveis */
	
    int vetor[10],n,i;

	/* Fim */

	/* Entrada de dados */
	
    for(i = 0;i<10;i++){

        setlocale(LC_ALL,"");
        printf("Digite %dº valor:",i+1);
        scanf("%d",&vetor[i]);
    }
	// Solicita que o usuário que entre com algum dado qualquer

    do{
        printf("Digite o valor a ser buscado:");
        scanf("%d",&n);

        //Buscando o valor usando busca binária interativa
        /* Saida de dados */
        printf("%d na posição %d",n,buscabinariainterativa(vetor,n,9));
        // Exibe mensagem na tela

    }while(n!=0);

	/* Fim */ 
 
	system("PAUSE"); // Apenas no Windows 
	return 0; // Pausa o programa para que ele não feche inesperadamente assim como o comando "getchar();" 

	


   } // Fim 

 

O que apresenta como resultado:

 

Note que não retorna  -1 quando não encontra o valor. Também já tentei com um valor que já foi adicionado no vetor.

[arfneto]

 

Seu código para a busca binária:

 

int buscabinariainterativa(int* vetor, int chave, int fim)
{
    int inicio = 0;
    int meio   = (inicio + fim) / 2;

    while (inicio <= fim)
    {
        if (chave == vetor[meio]) { return meio; }
        else
        {
            if (chave < vetor[meio]) { fim = meio - 1; }
            else
            {
                inicio = meio + 1;
            }
        }
    }

    return -1;
}

 

Notou que ele não é interativo? Porque esse nome então? O que é interativo é o loop do programa, que fica pesquisando até o usuário teclar '0'. E sobre isso pergunto: não seria mais simples continuar pesquisando até o cara teclar ENTER ao invés de um novo número? Afinal o cara pode querer pesquisar por um '0'...

 

A busca binária é um algoritmo iterativo, afinal é uma busca. Mas não é um algoritmo interativo.

 

Compare
 

    int buscabinariainterativa(int* vetor, int chave, int fim); // 1

    int busca_binaria_interativa(int* vetor, int chave, int fim); // 2

    int buscaBinariaInterativa(int* vetor, int chave, int fim); // 3

 

Qual acha mais simples de ler? E de todo modo podia ser só busca():

• interativa não é
• só tem um tipo de  busca no programa e é o objetivo do código afinal
   

        if (chave == vetor[meio]) { return meio; }
        else
        {

 

Evite esse tipo de construção:

• Não há razão para um else depois de um return. Só fica difícil de ler.
• Não há razão para chaves se só tem um comando. Só fica mais difícil de ler

Esse código faz o mesmo que o que escreveu. Compare

 

int busca(int* vetor, int chave, int fim)
{
    int inicio = 0;
    int meio   = (inicio + fim) / 2;

    while (inicio <= fim)
    {
        if (chave == vetor[meio]) return meio;
        if (chave < vetor[meio])
            fim = meio - 1;
        else
            inicio = meio + 1;
    }
    return -1;
}

 

Não acha que está errado não redefinir NUNCA o valor de meio mesmo vendo que muda o início ou o fim a cada loop? 

 

Sim, está errado. 

 

EXEMPLO

 

busca 32 em 11,12,13,14,15,16

 

• o meio vai começar com... 2. O elemento do meio então é 13
• 13 é menor que 32 então vai procurar agora na segunda metade, entre 14 e 16: [ 14,15,16 ]
• o meio agora é 4. O elemento do meio agora é 15. E você já vê que seu código está errado porque precisa redefinir o valor de meio já que naturalemente  ele depende de início e fim
• o elemento do meio, 15, é menor que 32. então vai procurar agora na segunda metade, entre 16 e 16: [ 16 ]
• 16 é o fim então está claro que não tem 32 no vetor

Compare

 

int busca(int* vetor, int busca, int fim)
{
    int inicio = 0;
    while (inicio <= fim)
    {
        int meio = (inicio + fim) / 2;
        if (busca == vetor[meio]) return meio;
        if (busca < vetor[meio])
            fim = meio - 1;
        else
            inicio = meio + 1;
    }
    return -1;
}

 

Que está certo.