PYTHON-PROGRAMM FÜR DIE BINÄRE SUCHE (REKURSIV UND ITERATIV)

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'> )>

Ausgabe

Element is present at index 3

Zeitkomplexität : O(log n)

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)

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

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