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.

1. Objektumorientált programozás

2. Öröklés a Java nyelven

3. Polymorphism in Java

4. Absztrakció a Java nyelven

5. „Java String”

6. Java Array

7. Java-gyűjtemények

8. Java szálak

9. Bevezetés a Java-szervletekbe

10. Szervlet és JSP oktatóanyag

11. Kivételkezelés Java-ban

12. „Java oktatóanyag”

13. Java interjúkérdések

14. Java programok

15. Kotlin vs Java

16. Függőség-injekció a Spring Boot használatával

17. Hasonlítható a Java-ban

18. A 10 legjobb Java-keretrendszer

19. Java Reflection API

20. A 30 legjobb minta a Java nyelven

21. Core Java Cheat Sheet

22. Socket Programming In Java

23. Java OOP Cheat Sheet

24. Annotations in Java

25. Könyvtárkezelő rendszer projekt Java nyelven

26. Fák Jáván

27. Machine Learning in Java

28. A Java legjobb adatstruktúrái és algoritmusai

29. Java fejlesztői készségek

30. Az 55 legnépszerűbb szervvel-interjúkérdés

31. Legjobb Java-projektek

32. Java Strings Cheat Sheet

33. Beágyazott osztály a Java-ban

34. Java Collections interjúkérdések és válaszok

35. Hogyan kezeljük a holtpontot Java-ban?

36. Az 50 legjobb Java-gyűjtemény interjúkérdése, amit tudnia kell

37. Mi a String Pool fogalma a Java nyelven?

38. Mi a különbség a C, a C++ és a Java között?

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

41. A Java programozási nyelv 10 legjobb alkalmazása

42. „Patthelyzet a Java-ban”

43. Négyzet és négyzetgyök Jáván

44. Gépírás Java nyelven

45. A Java operátorai és típusai

46. Destructor in Java

47. Bináris keresés a Java nyelven

48. MVC Architecture in Java

49. Hibernált interjú kérdések és válaszok

Eredetileg a https://www.edureka.co oldalon tették közzé 2019. augusztus 14-én.