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");
        }
    }    
 }
 }

Dúvidas ou sugestões? Deixem nos comentários! Para mais dicas, acesse o nosso canal no YouTube:
https://youtube.com/criandobits