Pesquisa binária em Java: coleções recursivas, iterativas e Java

A pesquisa linear em Java sempre foi o método ideal para encontrar um elemento em uma matriz. Ele pesquisa cada elemento do array sequencialmente e é extremamente fácil de implementar. No entanto, as deficiências da Pesquisa Linear são óbvias quando o array em questão contém dezenas de milhares de elementos. Nesses casos, o método “dividir e conquistar” implementado pela Pesquisa Binária é muito mais eficiente e preferível para programadores com complexidade de tempo e espaço em mente.

Pesquisa binária

Na Busca Binária, um array é repetidamente dividido em duas metades até que a chave (elemento que está sendo buscado) seja encontrada. A divisão é virtual, ou seja, a integridade dos dados é mantida. Com cada iteração, o valor do meio da matriz é focado. Se o valor for igual à chave que estamos procurando, o loop ou função recursiva termina. Caso contrário, ele continua em loop. Se o valor do meio for maior que a chave, a função se concentrará na primeira metade da matriz e vice-versa. Esse processo é repetido até que a chave seja encontrada ou todo o array tenha sido iterado.

Diferença entre pesquisa linear e binária

Algoritmo de Pesquisa Binária

O algoritmo de busca binária é dado abaixo.

1. Determine o primeiro e o último ponto da matriz. Os pontos serão ajustados a cada iteração de acordo com o array e a chave que está sendo pesquisada.
2. Percorra a matriz e compare o valor intermediário entre o primeiro e o último pontos atuais. Na primeira iteração, a primeira e a última variável serão iguais às reais do array.
3. Se a chave for maior que o valor do meio, o índice desse valor será armazenado na nova variável “First”.
4. Se a chave for menor que o valor do meio, o índice desse valor será armazenado na variável 'Last'.
5. Esta condição é repetida até que uma das duas condições se torne verdadeira:
   • A chave foi encontrada.
   • A matriz inteira foi iterada.

O código para pesquisa binária iterativa e pesquisa binária recursiva é fornecido abaixo.

Pesquisa Binária Iterativa

O código para pesquisa binária com um método iterativo é fornecido abaixo.

import java.util.Scanner;
public class IterativeBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;

        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Pesquisa Binária Recursiva

O código para Binário usando recursão é fornecido abaixo.

import java.util.Scanner;
public class RecursiveBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;

       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;

       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);

       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }

}

Complexidade de tempo

A cada iteração que passa, o array, ou seja, o espaço de busca é dividido pela metade. Após cada iteração 'm', o espaço de busca mudará para um tamanho de N/2m. Na pior das hipóteses, ficaremos apenas com um elemento em um lado distante da matriz. Neste momento, a complexidade da busca binária será k = log2N. A complexidade de tempo da busca linear é O(N), o que resulta em uma busca binária muito mais rápida com a complexidade O(log2N). Esse é o principal benefício de usar a pesquisa binária em vez da pesquisa linear.

Complexidade Espacial

A pesquisa binária usa três variáveis ​​diferentes — início, fim e meio. Essas três variáveis ​​são criadas como ponteiros que apontam para a localização de memória dos índices do array. Devido a isso, a pesquisa binária é extremamente eficiente com o espaço. A complexidade espacial da busca binária iterativa é O(1). Para implementação recursiva, é O(log N).