Ez a bemutató elmagyarázza a bináris keresést & Rekurzív bináris keresés Java-ban, valamint annak algoritmusát, végrehajtását és Java bináris keresési kódpéldákat:
A bináris keresés Java-ban egy olyan technika, amelyet egy gyűjteményben egy célzott érték vagy kulcs keresésére használnak. Ez egy olyan technika, amely az "oszd meg és uralkodj" technikát használja a kulcs keresésére.
A gyűjteményt, amelyre a bináris keresést kell alkalmazni egy kulcs kereséséhez, növekvő sorrendbe kell rendezni.
Általában a legtöbb programozási nyelv támogatja a lineáris keresést, a bináris keresést és a Hashing technikákat, amelyeket a gyűjteményben lévő adatok keresésére használnak. A hashingot a későbbi oktatóprogramokban fogjuk megtanulni.
Bináris keresés Java-ban
A lineáris keresés egy alapvető technika. Ebben a technikában a tömböt szekvenciálisan végigjárjuk, és minden egyes elemet a kulcshoz hasonlítunk, amíg a kulcsot meg nem találjuk, vagy el nem érjük a tömb végét.
A lineáris keresést a gyakorlati alkalmazásokban ritkán használják. A bináris keresés a leggyakrabban használt technika, mivel sokkal gyorsabb, mint a lineáris keresés.
A Java háromféleképpen végezhet bináris keresést:
- Az iteratív megközelítés alkalmazása
- Rekurzív megközelítés alkalmazása
- Az Arrays.binarySearch () módszer használata.
Ebben a bemutatóban mindhárom módszert megvalósítjuk és megvitatjuk.
Algoritmus bináris kereséshez Java-ban
A bináris keresési módszerben a gyűjteményt ismételten felére osztjuk, és a kulcselemet a gyűjtemény bal vagy jobb felében keressük attól függően, hogy a kulcs kisebb vagy nagyobb, mint a gyűjtemény középső eleme.
Egy egyszerű bináris keresési algoritmus a következő:
- A gyűjtemény középső elemének kiszámítása.
- Hasonlítsa össze a kulcselemeket a középső elemmel.
- Ha kulcs = középső elem, akkor a talált kulcs középső indexpozícióját adjuk vissza.
- Máskülönben Ha kulcs> középső elem, akkor a kulcs a gyűjtemény jobb felében van. Ismételje meg tehát az 1-3. lépést a gyűjtemény alsó (jobb) felén.
- Else key <középső elem, akkor a kulcs a gyűjtemény felső felében van. Ezért meg kell ismételni a bináris keresést a felső felében.
Amint a fenti lépésekből látható, a bináris keresésnél a gyűjtemény elemeinek felét az első összehasonlítás után figyelmen kívül hagyjuk.
Megjegyezzük, hogy ugyanaz a lépéssorozat érvényes az iteratív és a rekurzív bináris keresésre is.
Mutassuk be a bináris keresési algoritmust egy példán keresztül.
Vegyük például a következő 10 elemű rendezett tömböt.
Számítsuk ki a tömb középső helyét.
Közép = 0+9/2 = 4
#1) Kulcs = 21
Először is, összehasonlítjuk a kulcs értékét a [mid] elemmel, és megállapítjuk, hogy az elem értéke a közepénél = 21.
Így azt találjuk, hogy key = [mid], tehát a kulcs a tömb 4. pozíciójában található.
#2) Kulcs = 25
Először összehasonlítjuk a kulcs értékét a középértékkel. Mivel (21 <25), közvetlenül a tömb felső felében keressük a kulcsot.
Most ismét megkeressük a tömb felső felének középső értékét.
Közép = 4+9/2 = 6
Az érték a [mid] helyen = 25
Most összehasonlítjuk a kulcselemet a középső elemmel. Tehát (25 == 25), tehát megtaláltuk a kulcsot a [középső] = 6 helyen.
Így ismételten felosztjuk a tömböt, és a kulcselemet a középsővel összehasonlítva döntjük el, hogy melyik felében keressük a kulcsot. A bináris keresés idő és helyesség szempontjából hatékonyabb, és sokkal gyorsabb is.
Bináris keresés végrehajtása Java
A fenti algoritmus felhasználásával implementáljunk egy bináris kereső programot Java nyelven az iteratív megközelítéssel. Ebben a programban veszünk egy példatömböt, és bináris keresést végzünk ezen a tömbön.
import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println("A bemeneti tömb: " + Arrays.toString(numArray)); //a keresendő kulcs int key = 20; System.out.println("\nKey to be searched=" + key); //az elsőt az első indexre állítjuk int first = 0; //az utolsót a tömb utolsó elemére állítjuk int last=numArray.length-1; // kiszámítjuk a tömb közepét.tömb int mid = (first + last)/2; //míg az első és az utolsó nem fedik egymást while( first <= last ){ //ha a mid <kulcs, akkor a keresett kulcs a tömb első felében van if ( numArray[mid] last ){ System.out.println("Az elem nem található!"); } } } }
Kimenet:
A bemeneti tömb: [5, 10, 15, 20, 25, 30, 35]
Keresett kulcs=20
Az elem az indexen található: 3
A fenti program a bináris keresés iteratív megközelítését mutatja be. Kezdetben egy tömböt deklarálunk, majd meghatározzuk a keresendő kulcsot.
A tömb közepének kiszámítása után a kulcsot összehasonlítjuk a középső elemmel. Ezután attól függően, hogy a kulcs kisebb vagy nagyobb, mint a kulcs, a kulcsot a tömb alsó vagy felső felében keressük.
Rekurzív bináris keresés Java-ban
A bináris keresést a rekurziós technikával is elvégezheti. Itt a bináris keresési módszer rekurzívan meghívásra kerül, amíg a kulcsot meg nem találja, vagy a teljes lista ki nem merül.
A rekurzív bináris keresést megvalósító program az alábbiakban látható:
import java.util.*; class Main{ //rekurzív módszer bináris keresésre public static int binary_Search(int int intArray[], int low, int high, int key){ //ha a tömb rendben van, akkor bináris keresést végzünk a tömbön if (high>=low){ //számoljuk ki a közepet int mid = low + (high - low)/2; //ha key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //ha intArray[mid]> key akkor a kulcs balra van.a tömb fele if (intArray[mid]> kulcs){ return binary_Search(intArray, low, mid-1, kulcs);//rekurzívan keressük a kulcsot }else //kulcs a tömb jobb felében van { return binary_Search(intArray, mid+1, high, kulcs);//rekurzívan keressük a kulcsot } } return -1; } public static void main(String args[]){ //tömb és kulcs meghatározása int int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println("InputLista: " + Arrays.toString(intArray)); int key = 31; System.out.println("\nA keresett kulcs:" + key); int high=intArray.length-1; //a bináris keresési módszer hívása int result = binary_Search(intArray,0,high,key); //kiírja az eredményt if (result == -1) System.out.println("\nKulcs nem található a megadott listában!"); else System.out.println("\nKulcs a következő helyen található: "+result + " a listában"); } } }
Kimenet:
Bemeneti lista: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
A keresendő kulcs:
A kulcs a következő helyen található: 3 a listában
Az Arrays.binarySearch () módszer használata.
A Java Arrays osztálya rendelkezik egy 'binarySearch ()' metódussal, amely bináris keresést végez a megadott Array-n. Ez a metódus a tömböt és a keresendő kulcsot veszi argumentumként, és visszaadja a kulcs pozícióját a tömbben. Ha a kulcs nem található, akkor a metódus -1-et ad vissza.
Az alábbi példa az Arrays.binarySearch () metódust valósítja meg.
import java.util.Arrays; class Main{ public static void main(String args[]){ //meghatározunk egy tömböt int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println("A bemeneti tömb : " + Arrays.toString(intArray)); //meghatározzuk a keresendő kulcsot int key = 50; System.out.println("\nA keresendő kulcs:" + key); //hívjuk a binarySearch módszert a megadott tömbön a keresendő kulccsal int result =Arrays.binarySearch(intArray,key); //kiírja a visszatérési eredményt if (result <0) System.out.println("\nKey nem található a tömbben!"); else System.out.println("\nKey indexen: "+result + " található a tömbben."); } } }
Kimenet:
A bemeneti tömb : [10, 20, 30, 40, 50, 60, 70, 80, 90]
A keresendő kulcs:50
A kulcs a tömb 4-es indexénél található.
Gyakran ismételt kérdések
K #1) Hogyan írunk bináris keresést?
Válasz: A bináris keresés általában a tömb felére osztásával történik. Ha a keresendő kulcs nagyobb, mint a középső elem, akkor a tömb felső felét keressük a tömb további felosztásával és az altömb keresésével, amíg a kulcsot meg nem találjuk.
Hasonlóképpen, ha a kulcs kisebb, mint a középső elem, akkor a kulcsot a tömb alsó felében keressük.
K #2) Hol használják a bináris keresést?
Válasz: A bináris keresést főként szoftveralkalmazásokban használják a rendezett adatok keresésére, különösen akkor, ha a memóriaterület kompakt és korlátozott.
3. kérdés) Mi a bináris keresés nagy O-ja?
Válasz: A bináris keresés időbonyolultsága O (logn), ahol n a tömb elemeinek száma. A bináris keresés térbonyolultsága O (1).
Q #4) A bináris keresés rekurzív?
Válasz: Igen, mivel a bináris keresés egy példa az oszd meg és uralkodj stratégiára, és rekurzióval valósítható meg. A tömböt felezhetjük, és ugyanazt a módszert hívhatjuk meg a bináris keresés újra és újra történő végrehajtásához.
Q #5) Miért hívják bináris keresésnek?
Válasz: A bináris keresési algoritmus egy oszd meg és uralkodj stratégiát használ, amely a tömböt ismételten felére vagy két részre vágja. Ezért nevezik bináris keresésnek.
Következtetés
A bináris keresés a Java-ban gyakran használt keresési technika. A bináris keresés feltétele, hogy az adatokat növekvő sorrendbe rendezzük.
A bináris keresés megvalósítható iteratív vagy rekurzív megközelítéssel. A Java Arrays osztálya is rendelkezik a 'binarySearch' metódussal, amely bináris keresést hajt végre egy Array-n.
A következő oktatóanyagainkban különböző rendezési technikákat fogunk felfedezni Java-ban.