Question

Uma aplicação mantém um grande conjunto de dados ordenados em uma lista linear em memória,
implementada na forma de array. Os dados são estáveis, ou seja, são realizadas poucas operações de inserção
e remoção, e a aplicação exige grande quantidade de pesquisas. Sabe-se que vários algoritmos permitem
realizar pesquisas em um conjunto de dados, sendo alguns mais eficientes que outros. Nesse sentido, a
pesquisa binária apresenta caracteristicas bem definidas para se encontrar um dado procurado.
Considerando o contexto apresentado, desenvolva um algoritmo de pesquisa binária, de forma imperativa ou
orientada objetos, utilizando qualquer notação em português estruturado ou em uma linguagem de alto
nível, como o Pascal, C ou Java.

Answer 1

Resposta:

Pesquisa Binária é um algoritmo de busca ou de pesquisa que encontra um determinado elemento em um array ordenado. O algoritmo compara o elemento sendo procurado com o elemento na posição do meio do array. Se eles forem diferentes , o algoritmo prossegue na metade onde o elemento pode se localizar ; se o elemento sendo procurado for menor que o elemento do meio , a busca prossegue na metade inferior do array ; caso contrario prossegue na metade superior do mesmo. Assim , o requisito para a utilização desse algoritmo é que os dados estejam ordenados.

Solução iterativa:

// x: valor a ser pesquisado, n: tamanho do vetor, v: vetor de valores

// Se encontrar, retorna o índice do vetor, senão retorna -1

    int busca Binaria (int x, int n, int v[]) {

    int e, m, d;  

    e = 0;

    d = n – 1;

     while (e <= d) {

     m = (e + d) / 2

      if (v[m] == x)      

      return m

      }

      Solução recursiva:

      // x: valor a ser pesquisado, e: índice do início da pesquisa,

     //    d: índice do fim da pesquisa, v: vetor de valores

    // Se encontrar, retorna o índice do vetor, senão retorna -1

    nt buscaBinaria(int x, int e, int d, int v[]) {

    nt m;

    if (e <= d) {

    m = (e + d) / 2

    if (v[m] == x)    

    return m;

    if (v[m] < x)      

    return buscaBinaria(x, m+1, d, v);  

    else    

    return buscaBinaria(x, e, m-1, v);

    }  

   else    

   return -1

   }

Explicação:

Enade

Referências

1.  AHO, Alfred  V.  Foundations of computer science. New York: Computer Science Press, 1998.

2.  CORMEN, Thomas H.  Introduction to algorithms. 3. ed. Cambridge: The MIT Press, 2009.