Algoritmos com Java: Busca Binária

Na série "Algoritmos com Java" iremos compartilhar alguns algoritmos que implementamos com Java. Segue abaixo uma implementação de Busca Binária. Notem que há bastante uso de Java 8 na parte que tratamos a entrada do usuário.

	public class BuscaBinaria {
	/*
	* Ao executar passe uma lista de números separados por vírgulas: java BuscaBinaria 5 1,2,3,4,5
	* O primeiro número é que você irá buscar e em seguida vem a lista dos números onde a busca será feita.
	* Não copiei o programa, gosto de programar em Java.
	*/
	public static void main(String args[]) {
	if(args.length < 2) {
	System.out.println("Preciso que você me passe os números separadas por vírgulas!");
	System.out.println("Exemplo de execução:");
	System.out.println("java BuscaBinaria 1,3,5,9,10,15,100,202,413,500 1");
	}
	String numsStr[] = args[0].split("\\,");
	int x = Integer.parseInt(args[1]);
	System.out.println("Buscando " + x + " no seguinte vetor: ");
	int nums[] = java.util.stream.Stream.of(numsStr)
	.map(String::trim)
	.mapToInt(Integer::parseInt)
	.peek(System.out::println)
	.toArray();
	int pos = buscaBinaria(nums, x);
	System.out.printf("\n**%d %s**\n", x, (pos == -1? "não encontrado":"encontrado na posição " + (pos +1)));
	}
	/*
	* Realiza a busca binaria de x em numeros, retornando -1 o index se não for encontrado
	*/
	public static int buscaBinaria(int[] numeros, int x) {
	int pos = -1, posInicial = 0, posFinal = numeros.length - 1;
	while(posInicial <= posFinal) {
	pos = (posFinal + posInicial) / 2;
	if(numeros[pos] == x) return pos;
	else if(numeros[pos] > x) posFinal = pos - 1;
	else posInicial = pos + 1;
	};
	return -1;
	}
	}

view raw BuscaBinaria.java hosted with ❤ by GitHub

Aqui está um exemplo de uso:

Para rodar copiem o código acima em um arquivo chamado BuscaBinaria.java, compilem com Java 8 usando javac e executem usando java passando a lista de números separados por vírgula e o que deve ser buscado separado por um espaço.
Notem que essa é uma possível implementação, há outras formas que não iremos discutir nem comparar. Os tópicos de algoritmos ficarão aqui sempre tentando apimentar um pouco o algoritmo principal com Java 8 e 9, mas a implementação principal ficará sempre em um método separado, assim separamos a API da linguagem do algoritmo.
Em breve teremos mais algoritmos com Java!