Algoritmo de Busca Binária em Java: Rápida Localização em Arrays Ordenados

 

Explicação do Código

1. Entrada de Dados:
   • O usuário insere o tamanho e os elementos do array.
   • O programa ordena o array automaticamente usando Arrays.sort().
2. Busca Binária:
   • Usa ponteiros para dividir o array ao meio repetidamente.
   • A complexidade é $O(\log n)$, muito eficiente para grandes conjuntos de dados.
3. Saída:
   • Retorna a posição do elemento no array ordenado ou indica que ele não foi encontrado.

---

Exemplo de Execução

Entrada:

Digite o tamanho do array: 6
Digite os elementos do array (em qualquer ordem):
40 10 30 50 20 60
Array ordenado: [10, 20, 30, 40, 50, 60]
Digite o elemento que deseja buscar: 30

Saída:

Elemento encontrado na posição: 2

Entrada (buscando algo inexistente):

Digite o tamanho do array: 6
Digite os elementos do array (em qualquer ordem):
40 10 30 50 20 60
Array ordenado: [10, 20, 30, 40, 50, 60]
Digite o elemento que deseja buscar: 70

Saída:

Elemento não encontrado.

Veja o codigo para testa:
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Entrada de dados: tamanho do array
        System.out.print("Digite o tamanho do array: ");
        int n = scanner.nextInt();

        // Criando e preenchendo o array
        int[] array = new int[n];
        System.out.println("Digite os elementos do array (em qualquer ordem):");
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        // Ordenando o array
        Arrays.sort(array);
        System.out.println("Array ordenado: " + Arrays.toString(array));

        // Entrada do elemento a ser buscado
        System.out.print("Digite o elemento que deseja buscar: ");
        int elemento = scanner.nextInt();

        // Chama a função de busca binária
        int posicao = buscaBinaria(array, elemento);

        // Exibe o resultado da busca
        if (posicao != -1) {
            System.out.println("Elemento encontrado na posição: " + posicao);
        } else {
            System.out.println("Elemento não encontrado.");
        }

        scanner.close();
    }

    // Método para realizar a busca binária
    public static int buscaBinaria(int[] array, int elemento) {
        int inicio = 0;
        int fim = array.length - 1;

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

            if (array[meio] == elemento) {
                return meio; // Elemento encontrado
            } else if (array[meio] < elemento) {
                inicio = meio + 1; // Busca na metade direita
            } else {
                fim = meio - 1; // Busca na metade esquerda
            }
        }
        return -1; // Elemento não encontrado
    }
}