Busca binária em Java

A busca binária em Java é um algoritmo eficiente para encontrar um elemento em uma lista ordenada. Em vez de procurar cada elemento sequencialmente (como na busca linear), a busca binária divide a lista pela metade a cada passo, descartando metade dos elementos de cada vez. Este algoritmo é muito rápido, especialmente em grandes listas, e tem uma complexidade de tempo de O(log n).

Como funciona a busca binária

Para realizar a busca binária, a lista deve estar ordenada. O algoritmo funciona da seguinte forma:

1. Definimos os índices início e fim da lista.
   
   
2. Calculamos o índice meio como (início + fim) / 2.
   
   
3. Comparamos o valor do elemento no índice meio com o valor procurado:
   
   
   • Se for igual, o elemento foi encontrado.
     
     
   • Se o valor procurado for menor que o elemento do meio, descartamos a metade superior (ajustando o índice fim).
     
     
   • Se o valor procurado for maior, descartamos a metade inferior (ajustando o índice início).
     
     
4. Repetimos o processo até encontrar o elemento ou até que o índice de início ultrapasse o índice de fim.

Implementação da busca binária em Java

Vamos implementar a busca binária em Java de duas maneiras: iterativa e recursiva.

Abordagem 1: Implementação iterativa

A implementação iterativa usa um loop while para dividir a lista e procurar o valor desejado.

public class BuscaBinaria {
    public static int buscaBinaria(int[] array, int valor) {
        int inicio = 0;
        int fim = array.length - 1;

        while (inicio <= fim) {
            int meio = inicio + (fim - inicio) / 2;

            if (array[meio] == valor) {
                return meio; // Valor encontrado
            } else if (array[meio] < valor) {
                inicio = meio + 1; // Descarta a metade inferior
            } else {
                fim = meio - 1; // Descarta a metade superior
            }
        }
        return -1; // Valor não encontrado
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15};
        int valor = 7;
        int resultado = buscaBinaria(array, valor);

        if (resultado != -1) {
            System.out.println("Valor encontrado no índice: " + resultado);
        } else {
            System.out.println("Valor não encontrado.");
        }
    }
}

Saída:

Valor encontrado no índice: 3

Explicação do código:

• O índice meio é atualizado em cada iteração, dividindo a lista ao meio.
  
  
• Se o valor é encontrado, retornamos o índice.
  
  
• Se não encontramos o valor até que o índice início ultrapasse o índice fim, retornamos -1 para indicar que o valor não foi encontrado.

Abordagem 2: Implementação recursiva

A versão recursiva da busca binária chama a si mesma com uma lista reduzida, mantendo os valores de início e fim atualizados a cada chamada.

public class BuscaBinariaRecursiva {
    public static int buscaBinariaRecursiva(int[] array, int valor, int inicio, int fim) {
        if (inicio > fim) {
            return -1; // Valor não encontrado
        }

        int meio = inicio + (fim - inicio) / 2;

        if (array[meio] == valor) {
            return meio; // Valor encontrado
        } else if (array[meio] < valor) {
            return buscaBinariaRecursiva(array, valor, meio + 1, fim); // Metade superior
        } else {
            return buscaBinariaRecursiva(array, valor, inicio, meio - 1); // Metade inferior
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15};
        int valor = 7;
        int resultado = buscaBinariaRecursiva(array, valor, 0, array.length - 1);

        if (resultado != -1) {
            System.out.println("Valor encontrado no índice: " + resultado);
        } else {
            System.out.println("Valor não encontrado.");
        }
    }
}

Saída:

Valor encontrado no índice: 3

Explicação do código:

• A função buscaBinariaRecursiva verifica o valor do meio e chama a si mesma com uma nova faixa de índices, ajustando início ou fim conforme o caso.
  
  
• A recursão termina quando encontramos o valor ou quando inicio > fim.

Outro exemplo prático

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

A busca binária é um algoritmo fundamental para a pesquisa eficiente em listas ordenadas.

A versão iterativa é normalmente mais eficiente em termos de memória, enquanto a recursiva é mais elegante e fácil de entender.

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

Tags: busca binaria java