Traduzi a Busca Binária do livro "Entendendo Algoritmos" de Python para Java

Recentemente comentei sobre os dois repositórios que criei para documentar meus estudos de Java (mesmo com alguns códigos terríveis de iniciante lá no começo). Hoje queria falar sobre um código específico que subi no repositório Beecrowd-Algoritmos-em-Java, dentro da pasta CodigosLivro.

Estou lendo o livro “Entendendo Algoritmos: Um Guia Ilustrado” e o primeiro capítulo fala sobre a Busca Binária.

O conceito é bem simples. Imagina que você precisa adivinhar um número entre 1 e 100. A cada palpite, a pessoa te diz se o chute foi “muito alto” ou “muito baixo”. Se você for chutando em sequência (1, depois 2, depois 3…), e o número secreto for 100, no pior dos casos você vai tentar 100 vezes.

A ideia da busca binária é ser mais inteligente e começar pela metade. Você chuta 50. Se a pessoa disser “muito baixo”, você já eliminou metade da lista de uma vez só. Aí você chuta a metade do que sobrou (entre 50 e 100) e vai repetindo isso até encontrar o número. A grosso modo, é isso.

Depois dessa minha explicação simplificada, o livro mostra o algoritmo escrito em Python:

def pesquisa_binaria(lista, item): baixo = 0 alto = len(lista) - 1 while baixo <= alto: meio = (baixo + alto) // 2 chute = lista[meio] if chute == item: return meio if chute > item: alto = meio - 1 else: baixo = meio + 1 return Noneminha_lista = [1, 3, 5, 7, 9]print(pesquisa_binaria(minha_lista, 3)) # => 1print(pesquisa_binaria(minha_lista, -1)) # => None

O meu intuito aqui não é explicar o algoritmo a fundo (leiam o livro, é muito bom!), mas sim compartilhar o que eu fiz.

Eu consigo ler e entender Python, mas não sei escrever muito bem. Por outro lado, estudei Estrutura de Dados em C na faculdade. Então, peguei essa minha base de C e tentei “traduzir” esse código Python para o Java que estou estudando agora. Foi bem interessante, eu nunca tinha feito isso.

Com certeza deve existir uma implementação melhor ou mais “idiomática” em Java para isso, mas foi o que eu consegui fazer com meu conhecimento atual:

package CodigosLivro;import java.util.Random;public class BuscaBinaria { public static void main(String[] args) { // 'Sortear' um numero aleatorio entre 0 e 99 Random random = new Random(); int item = random.nextInt(100); System.out.println("Numero aleatorio: " + item); // Declarar, alocar e preencher um array de 100 posições ordenado int[] lista = new int[100]; for(int i = 0; i < 100; i++) { lista[i] = i; } int baixo = 0; int alto = (lista.length) - 1; // length é a quantidade de elementos no array while(baixo <= alto) { int meio = (baixo + alto) / 2; int chute = lista[meio]; if(chute == item) { System.out.println("Numero encontrado na posição: " + meio); break; // adicionei um break para parar o loop quando achar } if(chute > item) { alto = meio - 1; } else { baixo = meio + 1; } } }}

Vou continuar estudando Java e algoritmos, já que tenho muito o que aprender pela frente.

Muito obrigado pela atenção e até mais!