Kurz gesagt: Dieser Suchalgorithmus nutzt eine bereits sortierte Sammlung von Elementen aus, indem er die Hälfte der Elemente nach nur einem Vergleich ignoriert.
- Vergleiche x mit dem mittleren Element.
- Wenn x mit dem mittleren Element übereinstimmt, geben wir den mittleren Index zurück.
- Andernfalls, wenn x größer als das mittlere Element ist, kann x nur in der rechten (größeren) Hälfte des Subarrays nach dem mittleren Element liegen. Dann wenden wir den Algorithmus erneut für die rechte Hälfte an.
- Andernfalls muss das Ziel x in der linken (unteren) Hälfte liegen, wenn x kleiner ist. Also wenden wir den Algorithmus für die linke Hälfte an.
Python-Programm für die binäre Suche mit Rekursivität
Python3
# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> ># Check base case> >if> high>>=> low:> >mid>=> (high>+> low)>/>/> 2> ># If 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> >elif> arr[mid]>x:> >return> binary_search(arr, low, mid>-> 1>, x)> ># Else the element can only be present in right subarray> >else>:> >return> binary_search(arr, mid>+> 1>, high, x)> >else>:> ># Element is not present in the array> >return> ->1> # Test array> arr>=> [>2>,>3>,>4>,>10>,>40> ]> x>=> 10> # Function call> result>=> binary_search(arr,>0>,>len>(arr)>->1>, x)> if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> |
>
grep-Befehl unter Linux
>Ausgabe
Element is present at index 3>
Zeitkomplexität : O(log n)
Mehrzeiliger Powershell-Kommentar
Hilfsraum : O(logn) [HINWEIS: Rekursion erstellt Call Stack]
Python-Programm für die binäre Suche mit Iterativem
Python3
# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> >low>=> 0> >high>=> len>(arr)>-> 1> >mid>=> 0> >while> low <>=> high:> >mid>=> (high>+> low)>/>/> 2> ># If x is greater, ignore left half> >if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: high = mid - 1 # bedeutet, dass x in der Mitte vorhanden ist. Sonst: return mid # Wenn wir hier ankommen, war das Element nicht vorhanden. return -1 # Testarray arr = [ 2, 3, 4, 10, 40 ] x = 10 # Funktionsaufrufergebnis = Binary_search(arr, x) if result != -1: print('Element is present at index', str(result)) else: print('Element is not present in array ')> |
>
>Ausgabe
Element is present at index 3>
Zeitkomplexität : O(log n)
Methodenteilzeichenfolge Java
Hilfsraum : O(1)
Python-Programm für die binäre Suche unter Verwendung des integrierten Bisect-Moduls
Schritt-für-Schritt-Ansatz:
- Der Code importiert das Bisect-Modul, das Unterstützung für die binäre Suche bietet.
- Die Funktion „binary_search_bisect()“ ist definiert, die ein Array arr und das zu durchsuchende Element x als Eingaben verwendet.
- Die Funktion ruft die Funktion bisect_left() des Moduls bisect auf, die die Position des Elements im sortierten Array arr findet, an der x eingefügt werden sollte, um die sortierte Reihenfolge beizubehalten. Wenn das Element bereits im Array vorhanden ist, gibt diese Funktion seine Position zurück.
- Die Funktion prüft dann, ob der zurückgegebene Index i innerhalb des Bereichs des Arrays liegt und ob das Element an diesem Index gleich x ist.
- Wenn die Bedingung wahr ist, gibt die Funktion den Index i als Position des Elements im Array zurück.
- Wenn die Bedingung falsch ist, gibt die Funktion -1 zurück, was bedeutet, dass das Element nicht im Array vorhanden ist.
- Der Code definiert dann ein Array arr und ein zu durchsuchendes Element x.
- Die Funktion „binary_search_bisect()“ wird mit arr und x als Eingaben aufgerufen und das zurückgegebene Ergebnis wird in der Ergebnisvariablen gespeichert.
- Der Code prüft dann, ob das Ergebnis ungleich -1 ist, was darauf hinweist, dass das Element im Array vorhanden ist. Wenn „true“, wird die Position des Elements im Array ausgegeben.
- Wenn das Ergebnis gleich -1 ist, gibt der Code eine Meldung aus, dass das Element nicht im Array vorhanden ist.
Python3
Java und Swing
import> bisect> > def> binary_search_bisect(arr, x):> >i>=> bisect.bisect_left(arr, x)> >if> i !>=> len>(arr)>and> arr[i]>=>=> x:> >return> i> >else>:> >return> ->1> > > # Test array> arr>=> [>2>,>3>,>4>,>10>,>40>]> x>=> 10> > # Function call> result>=> binary_search_bisect(arr, x)> > if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> |
>
>Ausgabe
Element is present at index 3>
Zeitkomplexität : O(log n)
Hilfsraum : O(1)