A keresési és rendezési algoritmusok népszerű algoritmusok bármely programozási nyelvben. Ezek jelentik a programozás alapjainak megértését. Az egyik ilyen népszerű keresési algoritmus a Java bináris keresése. Ebben a cikkben mindent elmondok a megvalósításáról.
Ebben a cikkben az alábbi témákat tárgyaljuk:
- Mi az a bináris keresés?
- Bináris keresési algoritmus megvalósítása
- Rekurzív bináris keresés
Kezdjük el!
Mi az a bináris keresés?
A Java bináris keresése egy olyan keresési algoritmus, amely megkeresi a célérték pozícióját egy rendezett tömbön belül. A Bináris keresés a célértéket a tömb középső elemével hasonlítja össze. Csak az elemek rendezett halmazán működik. Ha bináris keresést szeretne használni egy gyűjteményben, először rendezni kell a gyűjteményt.
Ha a bináris keresést egy rendezett halmazon történő műveletek végrehajtására használjuk, az iterációk száma mindig csökkenthető a keresett érték alapján. A fenti pillanatképen láthatja a középső elem megtalálását. A bináris keresés analógiája az, hogy a tömb rendezéséről szóló információt használjuk, és az időbonyolítást O(log n)-re csökkentjük.
Bináris keresési algoritmus megvalósítása
Vessünk egy pillantást az alábbi pszeudo kódra, hogy jobban megértsük.
Procedure binary_search A ← sorted array n ← size of array x ← value to be searched
Set low = 1 Set high = n
while
x not found if
high < low EXIT: x does not exist.
set mid = low + ( high - low ) / 2
if
A[mid] < x set low = mid + 1
if
A[mid]> x set high = mid - 1
if
A[mid] = x EXIT: x found at location mid end while
end procedure
Magyarázat:
1. lépés: Először hasonlítsa össze x-et a középső elemmel.
2. lépés: Ha x egyezik a középső elemmel, akkor vissza kell adnia a középső indexet.
3. lépés: Egyébként, ha x nagyobb, mint a középső elem, akkor x csak a jobb oldali féltömbben lehet a középső elem után. Ezért megismétli a jobb felét.
4. lépés: Egyébként, ha (x kisebb), akkor ismételje meg a bal felét.
Így kell megkeresni az elemet az adott tömbben.
Lássuk most, hogyan lehet rekurzívan megvalósítani egy bináris keresési algoritmust. A program ugyanezt mutatja be.
Rekurzív bináris keresés
public
class
BinarySearch { // Java implementation of recursive Binary Search // Returns index of x if it is present in arr[l..h], else return -1 int
binarySearch(int
a[], int
l, int
h, int
x) { if
(h >= l) { int
mid = l + (h - l) / 2; // If the element is present at the middle itself if
(a[mid] == x) return
mid; // If element is smaller than mid, then it can only be present in left subarray if
(a[mid] >x) return
binarySearch(arr, l, mid - 1, x); // Else the element can only be present in right subarray return
binarySearch(arr, mid + 1, h, x); } // We reach here when element is not present in array return
-1; } public
static
void
main(String args[]) { BinarySearch ob = new
BinarySearch(); int
a[] = { 20, 30, 40, 10, 50
}; int
n = a.length; int
x = 40; int
res = ob.binarySearch(a, 0, n - 1, x); if
(res == -1) System.out.println("Element not present"); else System.out.println("Element found at index "
+ res); } }
A fenti program végrehajtásakor megkeresi az adott indexben található elemet
Element found at index 2
Így ezzel elérkeztünk a Bináris keresés Java-ban cikk végére. Remélem, informatívnak találta, és segített megérteni a Java alapjait.
Ezzel az Advanced Java Tutorial című blogunk végére értünk. Remélem, hogy ezt a blogot informatívnak találtad, és hozzáadott értéket a tudásodhoz.
Ha további cikkeket szeretnél megnézni a piac legfelkapottabb technológiáiról, mint például a mesterséges intelligencia, a DevOps, az Ethical Hacking, látogass el az Edureka hivatalos oldalára. .»
Nézze meg a sorozat további cikkeit, amelyek elmagyarázzák a Java különféle egyéb vonatkozásait.
5. „Java String”
6. Java Array
8. Java szálak
12. „Java oktatóanyag”
14. Java programok
15. Kotlin vs Java
26. Fák Jáván
36. Az 50 legjobb Java-gyűjtemény interjúkérdése, amit tudnia kell
39. Palindrom a Java-ban – Hogyan ellenőrizhetek egy számot vagy karakterláncot?
40. A legnépszerűbb MVC interjúkérdések és válaszok, amelyeket tudnod kell
42. „Patthelyzet a Java-ban”
Eredetileg a https://www.edureka.co oldalon tették közzé 2019. augusztus 14-én.