Tópicos Binária em Vetor

Objetivos

Após esta aula o aluno deverá:

1. saber explicar o princípio da busca binária em vetor;
2. ser capaz de implementar a busca binária em C

Referências

CORMEN, Thomas. Desmistificando Algoritmos. [Digite o Local da Editora]: Grupo GEN, 2013. 9788595153929. Disponível em: https://app.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em: 14 abr. 2022.

Conceitos Iniciais sobre a busca binária

É importante observar inicialmente que o vetor onde será realizada a busca deve estar ORDENADO.

A ideia subjacente é começar a pesquisa no MEIO do vetor. Três possibilidade podem ocorrer.

1. O item procurado está no meio do vetor, este caso o índice do meio deve ser retornado.
2. O item a ser procurado é MAIOR que o elemento do MEIO então a busca deve ser realizada no subvetor compreendido entre o MEIO +1 e o FINAL.
3. O item a ser procurado é MENOR que o elemento do MEIO então a busca deve ser realizada no subvetor compreendido entre o INICIO e o MEIO -1.

Note que o algoritmo deve então repetir a busca conforme as condições acima até que INICIO seja maior que o FIM (note que estes limites mudam a cada subvetor).

Ver figura de busca linear aqui

Algoritmo da Busca Binária

Ver

FUNCAO busca_binaria
DADOS DE ENTRADA:
   V: Vetor de itens /* para manter conformidade com o C, assumimos que a indexação começa em 0 */
   inteiro n: tamanho do vetor
   inteiro x: valor a ser procurado
DADOS DE SAÍDA
   índice do item encontrado (-1 se não encontrado)
VARIÁVEIS AUXILIARES
  inteiro i,
  inicio,
  fim,
  meio
INÍCIO
  inicio=0 /* supondo que o vetor começa na posição 0 */
  fim=n-1 
  ENQUANTO (inicio <= FIM) FAZ
     meio=(inicio+fim)/2 /* deve ser arredondado para o primeiro inteiro menor ou igual a divisão (floor) */
     SE V[meio]==x ENTAO /* se o item está no meio, então nada mais a fazer... retornar o índice do meio */
        retornar meio;
     SENAO SE V[meio] > x ENTAO
        fim = meio -1      /* reajusta os limites de forma a determinar um subvetor inferior  */
     SENAO  SE V[meio] < x ENTAO         
        inicio  = meio + 1 /* reajusta os limites de forma a determinar um subvetor superior  */
  FIM_ENQUANTO
  retornar -1 /* se chegou aqui é porque não encontrou ... Retorna -1 */
FIM

EXERCÍCIO 1: Implementar uma função C para o algoritmo de busca acima. Testar 4 vezes de forma a cobrir todas as possibilidades de saída.