Algoritmo de pesquisa binária (Binary Search) em Java

O Algoritmo de Pesquisa Binária é um método eficiente de Java programação, usado para encontrar um valor específico dentro de um array ordenado. Esta abordagem divide continuamente o array em duas partes e compara o valor da pesquisa com o elemento do meio.

Como funciona o algoritmo de pesquisa binária

O algoritmo de pesquisa binária começa comparando o valor da pesquisa com o elemento intermediário da matriz. Se o valor da pesquisa for igual ao elemento do meio, o algoritmo retorna a posição desse elemento. Se o valor da pesquisa for menor que o elemento do meio, o algoritmo continua a pesquisa na metade esquerda do array. Se o valor da pesquisa for maior, o algoritmo continua a pesquisa na metade direita do array. Este processo se repete até que o valor de pesquisa seja encontrado ou não haja mais elementos para pesquisar.

Vantagens e desvantagens do algoritmo de pesquisa binária

Vantagens:

• Alta Eficiência: Este algoritmo elimina metade dos elementos em cada etapa, otimizando a busca por grandes arrays.
• Baixa complexidade de tempo: A complexidade de tempo deste algoritmo é O(log n), tornando-o eficaz para grandes conjuntos de dados.

Desvantagens:

• Requisito de matriz classificada: o algoritmo funciona apenas com matrizes classificadas.

Exemplo e explicação

Considere um exemplo de uso do algoritmo de pesquisa binária para encontrar um número inteiro específico em uma matriz de números inteiros classificada Java.

public class BinarySearchExample {  
    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; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

Neste exemplo, usamos o algoritmo de pesquisa binária para encontrar o número 9 em uma matriz de inteiros classificada. O algoritmo itera pela matriz e compara o valor de pesquisa com o valor intermediário. Nesse caso, o número 9 é encontrado na posição 4(índice baseado em 0) do array.

Embora este exemplo demonstre como o algoritmo de pesquisa binária pode encontrar um elemento em uma matriz de inteiros classificada, ele também pode ser aplicado a outros cenários de pesquisa na Java programação.