Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
igorsouza2012

Busca Binaria Recursiva

Recommended Posts

igorsouza2012

Galera meu programa esta com um problema... quando eu digito um numero maior que a metade do vetor ele nao acha.

Se eu digitar o meio ou um numero menor ele encontra normalmente...

Vou por o codigo quem puder me dar uma ajuda xD

int buscabinaria(int vet[n],int x)
{
int i,inicio,fim,meio,a;
inicio =0;
fim= n-1;
a=0;
    if (inicio>=fim)
    {
                    return 0;
    }
    else if (a==1)
    {
         return 1;
    }
    else
    {
        meio=(inicio+fim)/2;
        if (vet[meio]==x)
        {
            a=1;
            }
        else if (vet[meio]<x) // o erro deve estar nesse if, creio que na chamada recursiva só não consegui ver onde.
        {
             inicio=meio+1;
             return (vet,inicio);
             }
        else
        {
            fim=meio-1;
            return (vet,fim);
            }
    }
}   

Muito grato a quem puder ajudar.

Share this post


Link to post
Share on other sites
miguel4

boas

não estou a entender muito bem o objectivo do teu código.

Só para ver se percebo responde a algumas questões :

- O vector está ordenado?

- O "x" é o valor que estás a procurar vector ?

- Como estás a chamar a função ?

Se me responderes a isso talvez te possa ajudar.

Cumps.


keep it simple!

Share this post


Link to post
Share on other sites
yyajsayy

hey, é certo que não explicaste muito bem o que pretendes com essa função, se pretendes apenas fazer comparações e retornar o valor ou se bem entendi retornar a função com (o que é escusado) com o valor de inicio actualizado...

Pelo que percebi tens duas condições em cima escusadas.

Porque não simplificares o teu problema e fazeres um algoritmo mais soft..

Achas o meio, comparas, se for igual retornas, caso contrario vês para que lado pretendes ir, quando encontrares o valor retornas, senão retornas um valor negativo em caso de  "não encontrado o valor desejado".

Tipo assim:


int binaria(int *v, int tam, int x) {

int t = (tam / 2) - 1; //tens aqui o teu meio já definido

//verificar se valor medio é o teu x e retorna-lo, ficamos logo arrumados
if(v[t] ==x ) return t;


   //caso o x seja maior que o meio --> vamos pa direita até ao fim e retornamos
if(v[t] < x) {
    for(t = tam / 2; t < tam; t++) {
      if(v[t] == x) return t;
    }
  }

  //caso contrario vamos do meio <-- até ao inicio
  if(v[t] > x) {
    for(t = tam / 2; t > 0; t--) {
      if(v[t] == x) return t;
    }
  }


  //caso o valor nao conste no vector então retornamos -2 

  return -2;
}

Espero ter ajudado, cya


"If it don't work the first time, rename it to version 1.0."

http://seguranca-informatica.pt

Share this post


Link to post
Share on other sites
jpedro20

só uma coisa. No código acima utiliza ifs encadeados:

if(...)
else if(...)
else ...

como esta no codigo de cima se o do meio for logo o valor que pretendes ele vai continuar a analisar os outros casos (o que se torna desnecessario). Com ifs encadeados se encontrares o que pretendes ele não faz os outros casos.

Share this post


Link to post
Share on other sites
miguel4

boas

Para mim pesquisa binária é alguma coisa do género do que posto em baixo.

Mas para ela funcionar é necessário garantir todos os pontos que tinha postado antes para responderem.

E já agora yyajsayy , vai mas é trabalhar em S.O. que esse é avaliado :thumbsup:

cumps

PS: Função testada e a funcionar


bool binaria(int *v, int inicio,int final, int x) {

int meio;

if(inicio<final){
	meio=(final+inicio)/2;
	if(v[meio]==x){
		return true;
	}else{
		if(v[meio]<x)
			return binaria(v,meio+1,final,x);
		else
			return binaria(v,inicio,meio-1,x);
	}
}else{
	return false;
}
}


keep it simple!

Share this post


Link to post
Share on other sites
jpedro20

bool? não existe esse tipo nesta linguagem. Em C os booleanos são inteiros (0 e 1).

Share this post


Link to post
Share on other sites
miguel4

eu testei num compilador de c++ ( visual studio) mas em C ANSI tens dados do tipo boolean


keep it simple!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.