Wir teilen eine Sammlung von Elementen in der binären Suche in zwei Hälften auf, um die Anzahl der direkten Vergleiche zu verringern, die zum Entdecken eines Elements erforderlich sind. Allerdings gibt es eine Voraussetzung: Die Elemente des Arrays müssen vorher sortiert werden.
Binäre Suche
Der Binäre Suche Die Methode sucht den Index eines bestimmten Listenmitglieds. Es gehört zu den beliebtesten und schnellsten Algorithmen. Damit das Verfahren der binären Suche funktioniert, müssen die Einträge in der Liste sortiert sein.
Binäre Suche ist eine effizientere Suchtechnik zum Auffinden des Index eines Elements als Lineare Suche da wir nicht jeden Listenindex untersuchen müssen.
Die gesamte Funktionsweise des binären Suchalgorithmus kann in den folgenden Schritten zusammengefasst werden:
- Suchen Sie das mittlere Element im sortierten Array.
- Führen Sie einen Vergleich zwischen dem zu ortenden Element und dem mittleren Element durch.
- Wenn dieses Element mit dem mittleren Element der angegebenen Liste übereinstimmt, wird der Index des mittleren Elements zurückgegeben. Andernfalls vergleicht der Algorithmus das Element mit dem Element in der Mitte.
- Wenn nun das zu suchende Element größer als das mittlere Element der Liste ist, wird es mit der rechten Hälfte der Liste verglichen, d. h. mit Elementen nach dem mittleren Index.
- Oder wenn das Element kleiner als das Element in der Mitte der Liste ist, wird es nur mit der linken Hälfte der Liste verglichen, d. h. mit den Elementen vor dem mittleren Index.
Rekursive binäre Suche
Bei der binären Suche wird das Suchintervall kontinuierlich in zwei gleiche Teile geteilt, um ein Element in einem sortierten Array zu finden. Bei der wiederkehrenden binären Suche wird der gesamte binäre Suchvorgang in kleinere Teile zerlegt. Eine rekursive binäre Suche ist die rekursive Antwort auf eine binäre Suche.
Die folgenden Merkmale müssen alle rekursiven Lösungen erfüllen:
- Für einen rekursiven Ansatz ist ein Basisfall erforderlich.
- Bei einem rekursiven Ansatz muss es einen rekursiven Testfall geben.
- Ein rekursiver Ansatz muss dem Basisfall näher kommen.
Die unterste Unterteilung eines komplizierten Problems wird durch einen Basisfall dargestellt, der ein Endfall ist. Um also die binäre Suche mit der rekursiven Methode durchzuführen, muss unser Algorithmus einen Basisfall und einen rekursiven Fall enthalten, wobei der rekursive Fall zum Basisfall übergeht. Andernfalls würde der Prozess niemals abgeschlossen werden und zu einer Endlosschleife führen.
Die binäre Suchtechnik reduziert die Zeit, die zum Auffinden eines bestimmten Elements in einem sortierten Array benötigt wird. Die binäre Suchmethode wird häufig iterativ implementiert, wir können sie jedoch auch rekursiv implementieren, indem wir sie in kleinere Teile zerlegen.
Code
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
Ausgabe:
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
Rekursion ist eine äußerst leistungsfähige Programmier- und Problemlösungstechnik. Wir können es verwenden, um eine Vielzahl von Algorithmen auszuwerten und auszuführen, die von einfachen iterativen Problemen bis hin zu komplizierten Backtracking-Problemen reichen. In diesem Tutorial haben wir uns mit der Verwendung der Python-Sprache zum Erstellen der rekursiven binären Suchmethode befasst.