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:
- 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.
- Calcular o índice médio como a média dos limites inferior e superior: índice médio = (limite inferior + limite superior) / 2.
- Comparar o valor desejado com o elemento do vetor no índice médio.
- 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.
- 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.
- 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.
- 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.