Busca binária em Java
A busca binária, ou binary search, é um algoritmo que implementa o paradigma Divisão e Conquista para encontrar um elemento em um vetor ordenado. É a estratégia mais eficiente, mas necessita que o vetor esteja ordenado. Neste post veja busca binária em Java.
No algoritmo de pesquisa binária os dados do vetor são calculados para que seja dividido ao meio até que esteja no termo desejado:
import java.util.Scanner;
public class BuscaBinaria {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int db[] = new int[10];
int numero, i, inicio = 0, meio, fim = 9;
boolean localizador = false;
for (i = 0; i < 10; i++) {
System.out.print("Digite o " + (i + 1) + " número: ");
db[i] = in.nextInt();
}
System.out.println("Digite o número a ser localizado: ");
numero = in.nextInt();
i = 0;
//divide o vetor ao meio para iniciar a busca
meio = (inicio + fim) / 2;
//neste ponto o início começa na metade do vetor
while (inicio <= fim && localizador == false) {
//se de cara a posição onde o meio começou ter o valor buscado
if (db[meio] == numero) {
localizador = true; //localizado!
} else { //senão...
/* se o valor buscado for menor que o valor contido na posição meio do vetor...
if (numero < db[meio]) {
//então o fim do vetor passa a ser a sua metade - 1
//-1 para evitar comparar novamente o valor do meio do vetor
fim = meio - 1;
} else { // senão...
//então o início do vetor passa a ser a sua metade + 1
//+1 para evitar comparar novamente o valor do meio do vetor, que agora é
//o início de vetor
inicio = meio + 1;
}
//o meio do vetor sempre será o início + fim dividido por 2
meio = (inicio + fim) / 2;
}
}
if (localizador) {
System.out.println("Número encontrado na posição [" + meio + "]");
} else {
System.out.println("Número não encontrado");
}
}
}
}
Domine as boas práticas com projetos práticos que vão te ajudar a desenvolver sistemas e se destacar no mercado de programação.
Clique na imagem abaixo e conheça mais detalhes do nosso curso:
Link do curso: https://go.hotmart.com/S90628636G?src=siteCB
Dúvidas ou sugestões? Deixem nos comentários! Para mais dicas, acesse o nosso canal no YouTube:
https://youtube.com/criandobits