Dúvida em busca binária [Resolvido ]

boa tarde galera ! estou tentando desenvolver um pequeno programa que faça uma busca binária num pequeno vetor de números desordenados porém não estou conseguindo fazê-lo retornar mid = 4 que seria o certo, já que a[4] = 17; ( que é o valor que quero achar ) o pior de tudo, é que se eu colocar "do" não tenho retorno de nada, contudo o programa roda que é uma beleza, só que com erro de lógica . Obrigado a aqueles que puderem me ajudar !

Código:

#include <iostream>
using namespace std;

main ()
{
    int a[8] = {1,3,4,5,17,18,31,33} ;
    int low=0;
    int mid=0;
    int high = 7;
    int x= 17;
    int i=0;
   
    do{   
    if( low > high)
      return (-1);
    mid = (low + high ) / 2 ;
    if ( x== a[mid] )
      return(mid);
    if ( x < a[mid])
      for(i=a[low]; i< a[mid-1]; i++)
      { 
        if (a[i]==x)
        return x;
      } 
        else 
          low=mid+1 ;
          for(i=a[mid+1]; i<a[high]; i++)
          {
          if(a[i]==x)
          return x;
          }
      }while(a[i]!=17);
        cout << mid;       
        system("Pause");                 
}                           
     
   

A minha lógica estava totalmente errada, devido a eu não chamar a própria função através da recursividade, além do que não passei argumentos necessários à manipulação da busca.

Olá battlecry!

Você conseguiu resolver o problema?
Poste a versão certa do programa.
Algumas dicas:
* Não utilize tantos comandos return. Utilize o mesmo para retornar códigos de erros, saida do
switch/case e retorno de valor de função. Em um programa grande você terá dificuldade de acompanhar a execução do programa.

* No TC 2.0 para acompanhar a execução e depurar erros lógicos pode-se executar o programa passo-a-paso, utilizando o menu RUN + STEP OVER (F8) e monitorar as variáveis através de janela, menu BREAK/WATCH + ADD WATCH em seguida o nome da variável que será monitorada, pode monitorar várias delas repetindo o procedimento.

Se já souber utilizar esses recursos, desculpe, pelo menos tentei ajudar.
Um abraço,
Pestana.

Yo galera ! a lógica da busca binária é fazê-la através da recursividade, ou seja, fazer uma função chamar a si mesma; segue o algoritmo:

Obs. : eu o compilei no Dev C ++

/* o programa não está perfeito ( compila e funciona normalmente ) , porém tem um errinho de lógica XD mas é muito fácil de consertar aliás, existe uma forma até mais compacta de fazê-lo utilizando o operador ternário ' ? ' depois eu vou postar a versão compacta, primeiro preciso estudá-la XP um abraço a todos ! Ah, e professor Pestana, já foi decidido algo em relação as aulas de sábado e terça ? obrigado pelas dicas ! */
#include<stdio.h>

Código:

 int busca(int menor,int maior,int valor,int *vet);
 
 main()
 {
 
    int menor,maior;
    int valor;
    int vet[10]={2,3,6,9,12,16,18,25,36,40};
    int indice;
    printf("Digite o valor que deseja procurar no vetor: ");
    scanf("%d",&valor);
 
    menor=0;
    maior=9;
 
    indice=busca(menor,maior,valor,vet);
 
    if(indice !=-1)printf("Valor %d encontrado no vetor.",vet[indice]);
    else printf("O valor procurado nao existe no vetor.");
 
}

int busca(int menor,int maior,int valor, int *vet)
{
    int meio;
 
    if(menor>maior)
    return(-1);
  meio=(maior+menor)/2;
    if(valor==vet[meio])
      return(meio);
 
    if(valor<vet[meio])
        busca(menor,meio-1,valor,vet);
    else
        busca(meio+1,maior,valor,vet);
        return(valor);
}

bom o algoritmo com o operador ternário ficaria assim:

Código:

busca( int menor, int maior, int valor, *vet  )
{

  int meio=0;
  if ( menor > maior )
    return -1;
  meio=(menor + maior ) / 2 ;
  return ( valor == vet[meio] ? meio :  valor < vet[meio] ?
              busca( menor, meio -1, valor , vet) : busca( meio +1,  maior ,  valor, vet ) );
           
}

 

uma breve explicação sobre o algoritmo da busca binária : a busca binária consiste em você inicializar duas variáveis :
a que eu chamei de "menor " e "maior " estas por sua vez, serão armazenadas numa variável chamada meio mas por que isso ? para se ter eficiência, a busca binária primeiramente analisa se o vetor inicial vet[0] é maior que o último vet[9] se for não faz sentido continuar a análise então é retornado -1 . O seguinte processo é analisar se o dado que se deseja achar é igual ao do meio se for é mole né ? é só retornar meio que é a posição do valor desejado ( sendo que para se mostrar na tela o valor deve-se escrever vet [meio ] ) bom, feita a análise e descoberto que o valor NÃO é igual a meio é feita uma condição para saber se valor é menor que o valor do meio, se for ele irá procurar o valor em todos os elementos que forem menores que meio, se não for ( se valor for maior que meio ) a função fará uma busca aos elementos acima de meio; é por isso que a função deve chamar a si própria, pois a cada loop ela deverá fazer uma nova "varredura " atrás do elemento a ser achado.