Căutare binară în Java: Colecții recursive, iterative și Java

Căutarea liniară în Java a fost întotdeauna metoda de bază pentru a găsi un element într-o matrice. Căută secvențial fiecare element al matricei și este extrem de ușor de implementat. Cu toate acestea, deficiențele Căutării Liniare sunt evidente atunci când matricea în cauză conține zeci de mii de elemente. În astfel de cazuri, metoda „împărțiți și cuceriți” implementată de Binary Search este mult mai eficientă și de preferat pentru programatorii care au în vedere complexitatea timpului și spațiului.

Căutare binară

În căutarea binară, o matrice este împărțită în mod repetat în două jumătăți până când cheia (elementul care este căutat) este găsită. Diviziunea este virtuală, adică integritatea datelor este menținută. La fiecare iterație, valoarea de mijloc a matricei este focalizată. Dacă valoarea este egală cu cheia pe care o căutăm, bucla sau funcția recursivă se termină. În caz contrar, continuă să circule în buclă. Dacă valoarea din mijloc este mai mare decât cheia, funcția se concentrează apoi pe prima jumătate a matricei și invers. Acest proces se repetă până când cheia este găsită sau întreaga matrice a fost iterată.

Diferența dintre căutarea liniară și binară

Algoritmul de căutare binar

Algoritmul Căutării Binare este prezentat mai jos.

1. Determinați primul și ultimul punct al matricei. Punctele vor fi ajustate la fiecare iterație conform matricei și cheii căutate.
2. Iterați prin matrice și comparați valoarea de mijloc dintre primul și ultimul punct curent. În prima iterație, prima și ultima variabilă vor fi aceleași cu cele reale din matrice.
3. Dacă cheia este mai mare decât valoarea din mijloc, indexul acelei valori va fi stocat în noua variabilă „Prima”.
4. Dacă cheia este mai mică decât valoarea din mijloc, indexul acelei valori va fi stocat în variabila „Ultima”.
5. Această condiție se repetă până când una dintre cele două condiții devine adevărată:
   • Cheia este găsită.
   • Întreaga matrice a fost iterată.

Codul atât pentru căutarea binară iterativă, cât și pentru căutarea binară recursivă este prezentat mai jos.

Căutare binară iterativă

Codul pentru Căutarea binară cu o metodă iterativă este prezentat mai jos.

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;
    }
}

Căutare binară recursiv

Codul pentru Binary care utilizează recursiunea este prezentat mai jos.

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);
    }
 
}

Complexitatea timpului

Cu fiecare iterație care trece, matricea, adică spațiul de căutare este împărțit pe jumătate. După fiecare iterație „m”, spațiul de căutare se va schimba la o dimensiune de N/2m. În cel mai rău caz, vom rămâne cu un singur element pe o parte îndepărtată a matricei. În acest moment, complexitatea căutării binare va fi k = log2N. Complexitatea de timp a căutării liniare este O(N), ceea ce duce la căutarea binară mult mai rapidă cu complexitatea O(log2N). Acesta este avantajul principal al utilizării căutării binare în comparație cu căutarea liniară.

Complexitatea spațială

Căutarea binară utilizează trei variabile diferite - începutul, sfârșitul și mijlocul. Aceste trei variabile sunt create ca pointeri care indică locația de memorie a indicilor matricei. Din acest motiv, căutarea binară este extrem de eficientă cu spațiu. Complexitatea spațială a căutării binare iterative este O(1). Pentru implementarea recursivă, este O(log N).