Busca Binária e seus Principais Tipos em Java 8

A busca binária é um algoritmo de busca eficiente que opera em listas ordenadas, reduzindo o intervalo de busca pela metade a cada passo. Esse método é considerado uma das abordagens mais rápidas para encontrar um elemento em uma coleção de dados ordenada. Neste artigo, exploraremos a busca binária e alguns de seus principais tipos de implementação em Java 8.Fundamentos da Busca Binária


A busca binária é baseada no conceito de dividir para conquistar. Ela é aplicável somente a listas ordenadas, onde o processo é repetido até que o elemento seja encontrado ou o intervalo de busca seja reduzido a zero.

O algoritmo funciona da seguinte forma:Determine o índice do elemento médio da lista.
Compare o elemento médio com o valor procurado.
Se o elemento médio for igual ao valor procurado, a busca é concluída.
Caso contrário, se o elemento médio for menor que o valor procurado, descarte a metade inferior da lista. Se for maior, descarte a metade superior.
Repita os passos acima até encontrar o elemento ou o intervalo de busca se tornar vazio.
Implementação da Busca Binária em Java 8

java
public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
                return mid;

            if (array[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1; // Elemento não encontrado
    }

    public static void main(String[] args) {
        int[] sortedArray = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
        int target = 12;

        int result = binarySearch(sortedArray, target);

        if (result != -1)
            System.out.println("Elemento encontrado no índice: " + result);
        else
            System.out.println("Elemento não encontrado na lista.");
    }
}

Tipos de Busca Binária
Busca Binária Recursiva


A busca binária pode ser implementada de forma recursiva, dividindo a lista a cada chamada recursiva.

java
public class RecursiveBinarySearch {
    public static int recursiveBinarySearch(int[] array, int target, int left, int right) {
        if (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
                return mid;

            if (array[mid] < target)
                return recursiveBinarySearch(array, target, mid + 1, right);
            else
                return recursiveBinarySearch(array, target, left, mid - 1);
        }

        return -1; // Elemento não encontrado
    }

    public static void main(String[] args) {
        int[] sortedArray = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
        int target = 14;

        int result = recursiveBinarySearch(sortedArray, target, 0, sortedArray.length - 1);

        if (result != -1)
            System.out.println("Elemento encontrado no índice: " + result);
        else
            System.out.println("Elemento não encontrado na lista.");
    }
}

Busca Binária com Condições Especiais


Às vezes, pode ser necessário adaptar a busca binária para atender a certas condições específicas. Por exemplo, encontrar o primeiro elemento igual ou maior que um determinado valor.

java
public class SpecialBinarySearch {
    public static int findFirstGreaterOrEqual(int[] array, int target) {
        int left = 0;
        int right = array.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (array[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }

        return left; // Retorna o índice do primeiro elemento maior ou igual
    }

    public static void main(String[] args) {
        int[] sortedArray = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
        int target = 9;

        int resultIndex = findFirstGreaterOrEqual(sortedArray, target);

        if (resultIndex < sortedArray.length)
            System.out.println("Primeiro elemento maior ou igual encontrado no índice: " + resultIndex);
        else
            System.out.println("Não foi encontrado um elemento maior ou igual na lista.");
    }
}

Conclusão


A busca binária é uma técnica poderosa para encontrar elementos em listas ordenadas de maneira eficiente. Em Java 8, a implementação é direta, aproveitando as capacidades de manipulação de arrays. Além da busca binária tradicional, é possível adaptá-la para atender a requisitos específicos, como encontrar o primeiro elemento maior ou igual a um valor dado. Entender esses diferentes tipos de busca binária pode ser útil para otimizar a busca em diversas situações.