Wat is binair zoeken in Java? Hoe het te implementeren?

Zoek- en sorteeralgoritmen zijn de populaire algoritmen in alle programmeertalen. Ze vormen de basis om de basisprincipes van de programmering te begrijpen. Een zo'n populair zoekalgoritme is Binary Search in . In dit artikel vertel ik je alles over de implementatie ervan.

Onderstaande onderwerpen komen aan bod in dit artikel:

• Wat is binair zoeken?
• Implementatie van binair zoekalgoritme
• Recursieve binaire zoekopdracht

Laten we beginnen!

Wat is binair zoeken?

Binair zoeken in is een zoekalgoritme dat de positie van een doelwaarde binnen een gesorteerde array . Binaire zoekopdracht vergelijkt de doelwaarde met het middelste element van de array. Hetwerkt alleen op een gesorteerde set elementen. Om binair zoeken op een collectie te gebruiken, moet de moet eerst worden gesorteerd.

Wanneer de wordt gebruikt om bewerkingen uit te voeren op een gesorteerde set, het aantal iteraties kan altijd worden verminderd op basis van de waarde die wordt gezocht. U kunt in de bovenstaande momentopname zien hoe u het middenelement . De analogie van binair zoeken is om de informatie te gebruiken waarin de array is gesorteerd en de tijdcomplexiteit te verminderen tot O (logboek n) .

Implementatie van binair zoekalgoritme

Laten we de onderstaande pseudo-code eens bekijken om deze op een betere manier te begrijpen.

Procedure binary_search A & larr gesorteerde array n & larr grootte van array x & larr waarde die moet worden doorzocht Set low = 1 Set high = n terwijl x niet gevonden indien hoog
 Uitleg: 
 
 
 Stap 1: Vergelijk eerst x met het middelste element.
 Stap 2: Als x overeenkomt met het middelste element, moet je de middenindex teruggeven.
 Stap 3:  Anders, als x groter is dan het middenelement, dan kan x alleen in de rechter halve array na het middenelement liggen. Vandaar dat je de rechterhelft terugkeert.
 Stap 4: Anders, als (x kleiner is) dan terugkeren voor de linkerhelft.
Dat is hoe u naar het element in de gegeven array moet zoeken.
c ++ programma om een ​​array in oplopende volgorde te sorteren
Laten we nu eens kijken hoe we een binair zoekalgoritme recursief kunnen implementeren. Onderstaand programma laat hetzelfde zien.
 Recursieve binaire zoekopdracht 
openbare klasse BinarySearch {// Java-implementatie van recursieve binaire zoekactie // Geeft index van x terug als deze aanwezig is in arr [l..h], anders retourneert -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Als het element in het midden zelf aanwezig is if (a [mid] == x) retourneer mid // If element kleiner is dan mid, dan kan het alleen aanwezig zijn in de linker submatrix als (a [mid]> x) binarySearch retourneert (arr, l, mid - 1, x) // Anders kan het element alleen aanwezig zijn in de rechter submatrix return binarySearch (arr, mid + 1, h, x)} // We bereiken hier wanneer element niet aanwezig is 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 niet aanwezig') else System.out.println ('Element gevonden in index' + res)}}
Bij het uitvoeren van het bovenstaande programma, zal het het element lokaliseren dat aanwezig is in de specifieke index
Element gevonden bij index 2
Dit brengt ons dus aan het einde van de binaire zoekopdracht in Java artikel. Ik hoop dat je het informatief vond en je hebt geholpen het te begrijpen  .
 Bekijk de    door Edureka, een vertrouwd online leerbedrijf met een netwerk van meer dan 250.000 tevreden leerlingen verspreid over de hele wereld. We zijn hier om je te helpen bij elke stap op je reis, om naast deze Java-interviewvragen te worden. We bedenken een curriculum dat is ontworpen voor studenten en professionals die Java Developer willen worden. De cursus is bedoeld om u een voorsprong te geven in het programmeren van Java en u te trainen in zowel de kern als geavanceerde Java-concepten, samen met verschillende Java-frameworks zoals Hibernate & Spring. 
 Voor het geval u problemen ondervindt bij het implementeren van Binary Search in  , vermeld het dan in de commentaren hieronder  en we nemen zo spoedig mogelijk contact met u op.