Die binäre Suche ist eine der Suchtechniken, die beim Sortieren der Eingabe angewendet werden. Hier konzentrieren wir uns darauf, das mittlere Element zu finden, das als Referenzrahmen fungiert, unabhängig davon, ob wir nach links oder rechts dorthin gehen, da die Elemente bereits sortiert sind. Diese Suche hilft bei der Optimierung der Suchtechnik bei jeder Iteration. Sie wird als binäre Suche bezeichnet und die Leser machen sich darüber Sorgen, da sie indirekt zur Lösung von Fragen eingesetzt wird.
Binärer Suchalgorithmus in Java
Nachfolgend finden Sie den für die binäre Suche entwickelten Algorithmus:
- Start
- Nehmen Sie das Eingabearray und das Ziel
- Initialisiere Start = 0 und Ende = (Array-Größe -1)
- Mittlere Variable indianisieren
- Mitte = (Anfang+Ende)/2
- Wenn array[ mid ] == target, dann gebe mid zurück
- if array[ mid ]
- Wenn Array[Mitte]> Ziel, dann Ende = Mitte-1
- Wenn Start<=Ende, dann gehe zu Schritt 5
- Geben Sie -1 zurück, da kein Element gefunden wurde
- Ausfahrt
Jetzt müssen Sie sich fragen: Wenn die Eingabe nicht sortiert ist, sind die Ergebnisse undefiniert.
Notiz: Bei Duplikaten gibt es keine Garantie, welches Duplikat gefunden wird.
Methoden für die Java-Binärsuche
In Java gibt es drei zu implementierende Methoden Binäre Suche in Java werden unten erwähnt:
- Iterative Methode
- Rekursive Methode
- Inbuild-Methode
1. Iterative Methode für die binäre Suche in Java
Nachfolgend wird die Implementierung erwähnt:
Java
// Java implementation of iterative Binary Search> class> BinarySearch {> >// Returns index of x if it is present in arr[l....r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >while> (l <= r) {> >int> mid = (l + r) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x) {> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>Ausgabe
String-Format
Element found at index 3>
Tipp: Geeks, ihr fragt euch bestimmt, ob es eine solche Funktion gibt untere_grenze() oder obere Grenze() wahrscheinlich nur in C++ STL zu finden. Die klare Antwort ist also, dass es bis Java 9 keine Funktion gab, später wurden sie hinzugefügt.
2. Rekursive Methode für die binäre Suche
Nachfolgend finden Sie die Implementierung der oben genannten Methode:
Java
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// Returns index of x if it is present in arr[l..> >// r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >if> (r>= l) {> >int> mid = l + (r - l) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>Ausgabe
Element is present at index 3>
Komplexität der oben genannten Methode
Zeitkomplexität: O(log N)
Raumkomplexität: O(1), Wenn der rekursive Aufrufstapel berücksichtigt wird, ist der Hilfsraum O(log N)
3. In Build-Methode für die binäre Suche in Java
Arrays.binarysearch() funktioniert für Arrays, die auch einen primitiven Datentyp haben können.
Nachfolgend finden Sie die Implementierung der oben genannten Methode:
Java
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Ausgabe
22 found at index = 3 40 Not found>
Binäre Suche in Java-Sammlungen
Sehen wir uns nun an, wie Collections.binarySearch() für LinkedList funktioniert. Wie oben erläutert, läuft diese Methode grundsätzlich in log(n)-Zeit für eine Direktzugriffsliste wie ArrayList. Wenn die angegebene Liste die RandomAccess-Schnittstelle nicht implementiert und groß ist, führt diese Methode eine iteratorbasierte binäre Suche durch, die O(n)-Linkdurchläufe und O(log n)-Elementvergleiche durchführt.
Collections.binarysearch() Funktioniert für Objekte wie Sammlungen Anordnungsliste Und LinkedList .
Nachfolgend finden Sie die Implementierung der oben genannten Methode:
Java
// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Ausgabe
10 found at index = 3 15 Not found>
Die Komplexität der oben genannten Methode
Zeitkomplexität : O(log N)
Hilfsraum : O(1)