Busca Binária em Java

Introdução

A Busca Binária (Binary Search) é um algoritmo de busca eficiente usado para encontrar um valor em um array ordenado. É mais rápido que a busca linear porque elimina metade do array após cada iteração. Neste laboratório, aprenderemos os passos para implementar o algoritmo de busca binária em Java.

Criar um Array Ordenado

O algoritmo de busca binária requer um array ordenado, então primeiro criaremos um array ordenado.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Implementar a Busca Binária Iterativamente

Agora implementaremos o algoritmo de busca binária iterativamente. Este método retorna o índice do elemento se ele estiver presente no array. Caso contrário, retorna -1.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

Para executar o código, primeiro precisamos chamar o método binarySearchIterative, passar sortedArray e o elemento que queremos pesquisar como parâmetros.

## compile java file
javac BinarySearch.java

## run the file
java BinarySearch

Implementar a Busca Binária Recursivamente

Agora implementaremos o algoritmo de busca binária recursivamente. Este método também retorna o índice do elemento se ele estiver presente no array. Caso contrário, retorna -1.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

Para executar o código, precisamos chamar o método binarySearchRecursive, passar sortedArray, o elemento que queremos pesquisar, leftIdx e rightIdx como parâmetros.

Usar Métodos Embutidos para Busca Binária

Também temos funções embutidas em Java para implementar a busca binária. Essas funções são Arrays.binarySearch() e Collections.binarySearch(). Podemos usar essas funções para pesquisar um elemento em um array ordenado.

A função Arrays.binarySearch() recebe um array ordenado e um valor-chave (key value) a ser pesquisado como parâmetros. A função retorna o índice da chave se ela estiver presente no array. Caso contrário, retorna -1.

int index = Arrays.binarySearch(sortedArray, 6);

A função Collections.binarySearch() pode ser usada em coleções como ArrayLists para pesquisar um elemento. A função recebe a coleção ordenada e uma chave como parâmetros e retorna o índice em que a chave está presente. Caso contrário, retorna -1.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Teste

Agora testaremos todos os métodos e imprimiremos a saída.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

Para executar o código, primeiro compilamos o programa Java.

javac BinarySearch.java

Então podemos executar o programa.

java BinarySearch

Resumo

Este laboratório cobriu as etapas necessárias para implementar o algoritmo de busca binária (binary search) de forma iterativa e recursiva na linguagem de programação Java. Também aprendemos sobre os métodos embutidos Arrays.binarySearch() e Collections.binarySearch() para implementar a busca binária. Criamos um array ordenado e usamos diferentes métodos para pesquisar elementos nele.