Busca em vetor

[MABO]

saudações colegas,
tô tendo uma grande dificuldade em entender busca e inserção de elementos usando função.
int busca (int x, int n, int v[])
{
int k;
k = n-1;
while (k >= 0 && v[k] != x)
k -= 1;
return k;
}
algoritmo BUSCA (A, n, x)
i ← n
enquanto i > 0 E A[i] <> x faça
i ← i + 1
devolva x
Não tô conseguindo entender a lógica.

[Marcos Guedes]

Código:

int busca (int x, int n, int v[])
{
   /*
      int x: Elemento que pretendo procurar no vetor
      int n: Tamanho do vetor
      int v[]: Vetor onde farei a pesquisa
   */
   
   int k; // Variável auxiliar
   k = n-1; // A busca começará pelo último elemento
   
   while (k >= 0 && v[k] != x)
   {
      /*
         Este laço está procurando na posição "k" no vetor.
         A posição k inicialmente é o tamanho do vetor menos um.
         Obs: A primeira posição no vetor em C é "0"(ZERO), logo a última é "n-1"
      */
      /* É necessário decrementar 1 à variável k,
           para que a mesma dimunia até o valor 0, onde a
           condição while será encerrada
      */
      k -= 1; // Se você retirar esta linha, entrará num loop infinito.
   }
   /*
     Se o elemento desejado for encontrado, então a função
     irá retornar a posição do elemento no vetor.
     Caso contrário retornará "-1".
     O Fato de retornar -1 é porque esta posição é inexistente no vetor
   */
   return k;
}

Faça o seguinte teste:
1. Crie um vetor do tipo inteiro com 5 elementos, por exemplo.
2. Adicione os valores 1,2,3,4,5
3. Utilize a função para buscar o valor 6.

Ex:
busca (6, 5, seuVetor[])

Nota: Como este valor não existe em seu vetor, então você receberá -1 como resultado.

4. Tente buscando por um valor existente no vetor, 2.
Ex:
busca (2, 5, seuVetor[])

Nota: O retorno será 1, que é a posição do número 2 no vetor.

Espero ter esclarecido!
Qualquer dúvida, é só postar.

[MABO]

beleza ficou melhor, vamos diferenciar agora em busca busca sequencial recussiva.

int maximo_r (int n, int v[])
{
if (n == 1)
return v[0];
else {
int x;
x = maximo_r (n-1, v); /* máximo de v[0..n-2] */
if (x > v[n-1])
return x;
else
return v[n-1];
}
}
este é mais bonito que o anterior, pois tem recussão
algoritmo BUSCA-REC (A, n, x)
se n = 0 então
devolva 0
se A[n] = x então
devolva n
senão
devolva BUSCA-REC(A, n – 1, x)

[Marcos Guedes]

Estais com dúvidas em compreender este também?
Ou estais demonstrando outra forma?

[MABO]

Marcos por alguma razão este assunto tá me tirando o sono. Olha só o assunto é extenso e eu quero entender cada passo e um assunto por vez. então manda ai busca recussiva.
No nosso livro a linguagem é portucal, e como eu entendo melhor o C então tô colocando as duas linguagens. Beleza?

[Marcos Guedes]

Esta função está buscando pelo maior elemento do vetor!

Código:

int maximo_r (int n, int v[])
{
   /*
      int n: Tamanho do Array
      int v[]: Vetor onde será feita a pesquisa
   */
   if (n == 1)
   {
      /*
         A condição de parada deste algoritmo é para "n=1"
         (Esta verificação será realizada sempre que a função for chamada)
          Caso o vetor possua mais de um elemento, então,
          a busca no vetor será realizada recursivamente até estabelecer a condição
      */
      return v[0]; // Retorna o primeiro elemento
   }
   else
   {
         int x;
         /*
            Chamada recursiva!!!
            Observe que o primeiro parâmetro será sempre  subtraído.
            Ou seja, para cada chamada recursiva, é descartado o último elemento.
         */
         x = maximo_r (n-1, v);
         // "x" receberá o valor recursivo
         if (x > v[n-1])
            return x;
         else
            return v[n-1];
   }
}

MABO, recursão realmente é complicado de entender, e considero difícil de explicar também.
Mas vamos tentando para ver se conseguimos esclarecer.
rs...

Valores de entrada:
n = 3;
v = vetor[3,1,2];

Tentando explicar de forma prática:

Código:

1. maximo_r(3, [3,1,2]);
2.   3 == 1? Não! -> x = maximo_r(2,[3,1,2]);
3.                           2 == 1? Não! -> x = maximo_r(1, [3,1,2])
4.                                                   1 == 1? Sim! -> retorna 3 (v[0])

Chegamos ao final da última chamada recursiva!
A linha quatro foi resolvida, agora temos que resolver a linha três.

Repetindo o código até a linha 3:

Código:

1. maximo_r(3, [3,1,2]);
2.   3 == 1? Não! -> x = maximo_r(2,[3,1,2]);
3.                           2 == 1? Não! -> x = 3 // Este valor foi obtido na linha 4
4.                                                   // Este é o if que compara "if (x > v[n-1])"
5.                                                   3 > 1? Sim! -> Retorna 3 (return x)

Chegamos ao final da segunda chamada recursiva!
A linha três foi resolvida na linha cinco, agora temos que resolver a linha dois.

Repetindo até a linha 2:
1. maximo_r(3, [3,1,2]);
2. 3 == 1? Não! -> x = 3 // Este valor foi obtido na linha 3
3. // Este é o if que compara "if (x > v[n-1])"
4. 3 > 1? Sim! -> Retorna 3 (return x)[/code]
Chegamos ao final da primeira chamada recursiva!
A linha dois foi resolvida na linha quatro, agora temos que resolver a linha um.

Para resolvermos a linha um, novamente repetiremos até a linha 2:

Código:

1. maximo_r(3, [3,1,2]);
2.   3 == 1? Não! -> x = 3 // Este valor foi obtido na linha 2
                              // Este é o if que compara "if (x > v[n-1])"
                              3 > 2? Sim! -> Retorna 3 (return x)

Não sei se deu para ser claro, mas neste exemplo para uma entrada v[3,1,2]
Obtivemos o valor "3" com resultado.

Espero ter ajudado!

[MABO]

vou dá uma olhada, com mais calma. muito grato.

[Marcos Guedes]

Conseguisse resolver o problema, Mabo?

[MABO]

conseguir sim muito agradecido.