23 – Lógica de Programação – Pesquisa Binária em Vetores (Arrays)

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.

 

Sobre Fábio dos Reis (1195 Artigos)
Fábio dos Reis trabalha com tecnologias variadas há mais de 30 anos, tendo atuado nos campos de Eletrônica, Telecomunicações, Programação de Computadores e Redes de Dados. É um entusiasta de Ciência e Tecnologia em geral, adora Viagens e Música, e estuda idiomas, além de ministrar cursos e palestras sobre diversas tecnologias em São Paulo e outras cidades do Brasil.
Contato: Website

4 Comentários em 23 – Lógica de Programação – Pesquisa Binária em Vetores (Arrays)

  1. Obrigado pelos vídeos Fábio estão sendo bem úteis para mim que estou iniciando na programação ainda.

    Você por acaso pensa em postar videos sobre C++ ?

    Obrigado!

  2. Adalberto // 19/02/2018 em 19:11 // Responder

    O vídeo está bem legal, porém cria uma certa confusão em relação aos valores das variáveis. Tem momentos que se refere ao “conteúdo” da variável e em outros se refere à “posição” das variáveis.
    Exemplo: Quando “Meio” = 5, apontando para o valor 4, mostra o valor “5” em “meio”. Quando “meio” = 8, apontando para o valor 7, mostra o valor “7” em “meio”.

  3. Tuzin dos programas craft // 13/09/2018 em 15:30 // Responder

    Adorei sua perfil picture Fabio :p kkkkkk rsrsrsrsr lol

Escreva um comentário

Seu e-mail não será divulgado


*