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
Lineáris keresés |
Bináris keresés |
Sorozatosan keresi a tömböt |
Két felére osztja a tömböt, amíg meg nem találja az értéket |
Bármilyen tömbbel működik |
Csak rendezett tömbökkel működik |
A bonyolultság O(N) |
A komplexitás O(log2N) |
Rendezett és rendezetlen tömbökön is dolgozhat |
Csak rendezett tömbökön valósítható meg. |
Kevésbé bonyolult a megvalósítás |
Bonyolultabb a megvalósítás |
Bináris keresési algoritmus
A bináris keresés algoritmusa alább látható.
- 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.
- 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.
- 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.
- 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.
- 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).
GO TO FULL VERSION