Tweet

Pesquisa Binária em Vetores (Arrays)

Um algoritmo de pesquisa binária é um método bastante eficiente para encontrar um determinado valor em um vetor ordenado. Ele funciona dividindo repetidamente o vetor ao meio (por isso “binário”) até que o valor desejado seja encontrado ou seja determinado que o valor não está presente no vetor.

Como funciona uma algoritmo de pesquisa binária

O funcionamento do algoritmo de pesquisa binária é o seguinte:

1. Definir os limites inferior e superior do vetor. O limite inferior é definido como o índice 0 e o limite superior como o índice do último elemento do vetor.
2. Calcular o índice médio como a média dos limites inferior e superior: índice médio = (limite inferior + limite superior) / 2.
3. Comparar o valor desejado com o elemento do vetor no índice médio.
4. Se o valor desejado for igual ao elemento do índice médio, a pesquisa é bem-sucedida e o índice médio é retornado como o índice onde o valor foi encontrado.
5. Se o valor desejado for menor que o elemento do índice médio, a pesquisa será repetida no subvetor à esquerda do índice médio. O novo limite superior será definido como o índice médio – 1 e o passo 2 será repetido.
6. Se o valor desejado for maior que o elemento do índice médio, a pesquisa será repetida no subvetor à direita do índice médio. O novo limite inferior será definido como o índice médio + 1 e o passo 2 será repetido.
7. Repetir os passos 2 e 3 até que o valor desejado seja encontrado ou os limites inferior e superior se cruzem. Se os limites inferior e superior se cruzarem sem encontrar o valor desejado, isso significa que o valor não está presente no vetor.

No vídeo a seguir explico com detalhes como realizar a pesquisa binária em vetores, usando português estruturado.

Códigos usados no vídeo

algoritmo "Pesquisa Binária"
 // Função : Estudar a pesquisa binária em vetores
 // Autor : Fábio dos Reis
 // Data : 18/09/2013
 var
 CONTADORA, CONTADORB: inteiro
 NUM, AUX: inteiro
 VET: vetor[1..10] de inteiro
 BUSCA: inteiro

 //Variáveis para busca binária:
 inicial, final, meio: inteiro
 dado_encontrado: logico

 inicio
 //Preencher o array criado

para CONTADORA de 0 ate 1 faca
   para CONTADORB de CONTADORA + 1 ate 2 faca
      se VET[CONTADORA] > VET[CONTADORB] entao
         AUX <-VET[CONTADORB]
         VET[CONTADORB] <- VET[CONTADORA]
         VET[CONTADORA] <- AUX
      fimse
   fimpara
fimpara

 //Exibir o vetor ordenado
 escreval ("Vetor ordenado. Preparado para busca binária:")
 para CONTADORA de 1 ate 10 faca
    escreval(VET[CONTADORA])
 fimpara
 escreval()

//Entrar com valor a pesquisar no vetor
 escreva ("Digite um valor para procurar no vetor:")
 leia (busca)

//Efetuar a pesquisa binária
inicial <- 1
final <- 10
dado_encontrado <- falso

enquanto (inicial <= final) e nao dado_encontrado faca
   meio <- (inicial + final) DIV 2
   se VET[meio] = busca entao
      dado_encontrado <- verdadeiro
   fimse
   se VET[meio] > busca entao
      final <- meio - 1
   senao
      inicial <- meio + 1
   fimse
fimenquanto

//Exibir Resultados da busca
se dado_encontrado = verdadeiro entao
  escreva ("Dado encontrado na posição", meio)
senao
  escreva ("Informação não encontrada no vetor")
fimse
fimalgoritmo

Conclusão

O algoritmo de pesquisa binária é eficiente porque a cada iteração, a metade do vetor é descartada como candidata, reduzindo pela metade o espaço de pesquisa. Em vez de percorrer linearmente todo o vetor, o algoritmo aproveita a ordenação do vetor para realizar buscas rápidas.

É importante notar que o algoritmo de pesquisa binária requer que o vetor esteja ordenado em ordem crescente ou decrescente. Caso contrário, o algoritmo não funcionará corretamente. Além disso, o desempenho do algoritmo de pesquisa binária é mais eficiente em vetores grandes, onde a diferença entre os métodos de pesquisa linear e binária se torna mais evidente.