Bináris keresés Java nyelven: Rekurzív, Iteratív és Java gyűjtemények

A Java lineáris keresése mindig is a tömb elemeinek megkeresésére használt módszer volt. A tömb minden elemében szekvenciálisan keres, és rendkívül könnyen megvalósítható. A Lineáris keresés hiányosságai azonban nyilvánvalóak, ha a kérdéses tömb több tízezer elemet tartalmaz. Ilyen esetekben a Binary Search által megvalósított „oszd meg és uralkodj” módszer sokkal hatékonyabb és előnyösebb az idő- és térkomplexitást szem előtt tartó programozók számára.

Bináris keresés

A bináris keresés során egy tömb ismételten két részre van osztva, amíg meg nem találja a kulcsot (keresett elemet). A felosztás virtuális, azaz az adatok sértetlensége megmarad. Minden iterációnál a tömb középső értéke fókuszál. Ha az érték megegyezik a keresett kulccsal, a ciklus vagy a rekurzív függvény véget ér. Ellenkező esetben tovább fut. Ha a középső érték nagyobb, mint a kulcs, akkor a függvény a tömb első felére fókuszál, és fordítva. Ezt a folyamatot addig ismételjük, amíg meg nem találjuk a kulcsot, vagy a teljes tömb meg nem ismétlődik.

A lineáris és a bináris keresés közötti különbség

Bináris keresési algoritmus

A bináris keresés algoritmusa alább látható.

1. Határozza meg a tömb első és utolsó pontját. A pontok minden iterációnál a tömbnek és a keresett kulcsnak megfelelően módosulnak.
2. Ismételje meg a tömböt, és hasonlítsa össze a középső értéket az aktuális első és utolsó pontja között. Az első iterációban az első és az utolsó változó megegyezik a tömbben lévő tényleges változókkal.
3. Ha a kulcs nagyobb, mint a középső érték, akkor ennek az értéknek az indexe az új „First” változóban kerül tárolásra.
4. Ha a kulcs kisebb, mint a középső érték, akkor ennek az értéknek az indexe az „Utolsó” változóban kerül tárolásra.
5. Ez a feltétel addig ismétlődik, amíg a két feltétel egyike teljesül:
   • A kulcs megtalálható.
   • A teljes tömb ismétlődött.

Az iteratív bináris keresés és a rekurzív bináris keresés kódja alább található.

Iteratív bináris keresés

Az iteratív módszerrel végzett bináris keresés kódja alább látható.

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

Rekurzív bináris keresés

A rekurziót használó bináris kód az alábbiakban található.

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

Idő összetettsége

Minden áthaladó iterációnál a tömb, azaz a keresési tér fele lesz. Minden 'm' iteráció után a keresési tér N/2 m méretűre változik. A legrosszabb esetben csak egy elem marad a tömb egyik távoli oldalán. Ekkor a bináris keresés bonyolultsága k = log2N lesz. A lineáris keresés időbonyolultsága O(N), ami azt eredményezi, hogy a bináris keresés sokkal gyorsabb az O(log2N) komplexitás mellett. Ez a bináris keresés használatának elsődleges előnye a lineáris kereséssel szemben.

A tér összetettsége

A bináris keresés három különböző változót használ – kezdet, vége és közepe. Ez a három változó mutatóként jön létre, amelyek a tömbindexek memóriahelyére mutatnak. Ennek köszönhetően a bináris keresés rendkívül hatékony a térben. Az iteratív bináris keresés térkomplexitása O(1). Rekurzív megvalósítás esetén ez O(log N).