In diesem Tutorial erfahren Sie, wie wir mit Python einen binären Suchalgorithmus anwenden können, um die Indexposition eines Elements in der angegebenen Liste zu finden.

Einführung

Eine binäre Suche ist ein Algorithmus zum Auffinden eines bestimmten Elements in der Liste. Angenommen, wir haben eine Liste mit tausend Elementen und müssen die Indexposition eines bestimmten Elements ermitteln. Mit dem binären Suchalgorithmus können wir die Indexposition des Elements sehr schnell finden.

Es gibt viele Suchalgorithmen, aber die binäre Suche ist unter ihnen am beliebtesten.

Ubuntu Build unerlässlich

Die Elemente in der Liste müssen sortiert werden, um den binären Suchalgorithmus anzuwenden. Wenn Elemente nicht sortiert sind, sortieren Sie sie zuerst.

Lassen Sie uns das Konzept der binären Suche verstehen.

Konzept der binären Suche

Im binären Suchalgorithmus können wir die Elementposition mit den folgenden Methoden ermitteln.

• Rekursive Methode
• Iterative Methode

Der Divide-and-Conquer-Ansatztechnik folgt die rekursive Methode. Bei dieser Methode wird eine Funktion immer wieder aufgerufen, bis sie ein Element in der Liste gefunden hat.

Java-Referenztypen

Eine Reihe von Anweisungen wird mehrmals wiederholt, um die Indexposition eines Elements in der iterativen Methode zu ermitteln. Der während Die Schleife wird zum Ausführen dieser Aufgabe verwendet.

Die binäre Suche ist effektiver als die lineare Suche, da wir nicht jeden Listenindex durchsuchen müssen. Die Liste muss sortiert werden, um den binären Suchalgorithmus zu erreichen.

Lassen Sie uns die binäre Suche Schritt für Schritt implementieren.

Wir haben eine sortierte Liste von Elementen und suchen nach der Indexposition 45.

[12, 24, 32, 39, 45, 50, 54]

Wir setzen also zwei Hinweise in unserer Liste. Ein Zeiger wird verwendet, um den kleineren aufgerufenen Wert zu bezeichnen niedrig und der zweite Zeiger wird verwendet, um den höchsten aufgerufenen Wert anzugeben hoch .

in SQL gegossen

Als nächstes berechnen wir den Wert des Mitte Element im Array.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

Jetzt vergleichen wir das gesuchte Element mit dem mittleren Indexwert. In diesem Fall, 32 ist ungleich zu Vier fünf. Wir müssen also einen weiteren Vergleich durchführen, um das Element zu finden.

Wenn die gesuchte Zahl der Mitte entspricht. Dann kehre zurück Mitte Andernfalls fahren Sie mit dem weiteren Vergleich fort.

Die zu suchende Zahl ist größer als die Mitte Zahl vergleichen wir die N mit dem mittleren Element der Elemente auf der rechten Seite Mitte und auf niedrig stellen niedrig = mittel + 1.

Ansonsten vergleichen Sie die N mit dem mittleres Element der Elemente auf der linken Seite von Mitte und eingestellt hoch Zu hoch = mittel - 1.

Wiederholen Sie diesen Vorgang, bis die gesuchte Nummer gefunden wird.

Implementieren Sie eine binäre Suche in Python

Zunächst implementieren wir eine binäre Suche mit der iterativen Methode. Wir werden eine Reihe von Anweisungen wiederholen und jedes Element der Liste iterieren. Wir werden den Mittelwert finden, bis die Suche abgeschlossen ist.

Java-Datum aktuell

Lassen Sie uns das folgende Programm der iterativen Methode verstehen.

Python-Implementierung

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

Erläuterung:

Im obigen Programm -

• Wir haben eine Funktion namens erstellt binäre Suche() Funktion, die zwei Argumente benötigt – eine zu sortierende Liste und eine zu durchsuchende Zahl.
• Wir haben zwei Variablen deklariert, um den niedrigsten und höchsten Wert in der Liste zu speichern. Dem Tief wird der Anfangswert 0 zugewiesen, hoch Zu len(list1) - 1 und Mitte 0.
• Als nächstes haben wir die deklariert während Schleife mit der Bedingung, dass die am niedrigsten ist gleich und kleiner als die höchste Die while-Schleife wird wiederholt, wenn die Nummer noch nicht gefunden wurde.
• In der while-Schleife ermitteln wir den Mittelwert und vergleichen den Indexwert mit der gesuchten Zahl.
• Wenn der Wert des Mittelindex kleiner ist als N , erhöhen wir den Mittelwert um 1 und weisen ihn zu. Die Suche verschiebt sich auf die linke Seite.
• Andernfalls verringern Sie den Mittelwert und weisen Sie ihn dem zu hoch . Die Suche wird auf die rechte Seite verschoben.
• Wenn n gleich dem Mittelwert ist, wird zurückgegeben Mitte .
• Dies geschieht bis zum niedrig ist gleich und kleiner als die hoch .
• Wenn wir das Ende der Funktion erreichen, ist das Element nicht in der Liste vorhanden. Wir geben -1 an die aufrufende Funktion zurück.

Lassen Sie uns die rekursive Methode der binären Suche verstehen.

Rekursive binäre Suche

Bei der binären Suche kann die Rekursionsmethode verwendet werden. Hier definieren wir eine rekursive Funktion, die sich selbst so lange aufruft, bis sie die Bedingung erfüllt.

np.argmax

Lassen Sie uns das obige Programm mithilfe der rekursiven Funktion verstehen.

Python-Programm

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

Ausgabe:

 Element is present at index 2 

Erläuterung

Das obige Programm ähnelt dem vorherigen Programm. Wir haben eine rekursive Funktion und ihre Grundbedingung deklariert. Die Bedingung ist, dass der niedrigste Wert kleiner oder gleich dem höchsten Wert ist.

• Die mittlere Zahl berechnen wir wie im letzten Programm.
• Wir haben das verwendet Wenn Anweisung, um mit der binären Suche fortzufahren.
• Wenn der Mittelwert der gesuchten Zahl entspricht, wird der Mittelwert zurückgegeben.
• Wenn der Mittelwert kleiner als der Wert ist, suchen wir nach unserer rekursiven Funktion binäre Suche() erneut und erhöhen Sie den Mittelwert um eins und weisen Sie ihn auf „Niedrig“ zu.
• Wenn der Mittelwert größer ist als der gesuchte Wert, dann unsere rekursive Funktion binäre Suche() erneut und verringern Sie den Mittelwert um eins und weisen Sie ihn auf niedrig zu.

Im letzten Teil haben wir unser Hauptprogramm geschrieben. Es ist das gleiche wie das vorherige Programm, der einzige Unterschied besteht darin, dass wir zwei Parameter im übergeben haben binäre Suche() Funktion.

Dies liegt daran, dass wir in der rekursiven Funktion den Anfangswerten „Low“, „High“ und „Mid“ nicht zuweisen können. Jedes Mal, wenn die Rekursive aufgerufen wird, wird der Wert für diese Variablen zurückgesetzt. Das wird das falsche Ergebnis liefern.

Komplexität

Die Komplexität des binären Suchalgorithmus beträgt O(1) für den besten Fall. Dies geschieht, wenn das gesuchte Element im ersten Vergleich gefunden wird. Der O(logn) ist die schlechteste und durchschnittliche Fallkomplexität der binären Suche. Dies hängt von der Anzahl der Suchvorgänge ab, die durchgeführt werden, um das gesuchte Element zu finden.

Abschluss

Ein binärer Suchalgorithmus ist die effizienteste und schnellste Möglichkeit, ein Element in der Liste zu durchsuchen. Der unnötige Vergleich wird übersprungen. Wie der Name schon sagt, gliedert sich die Suche in zwei Teile. Der Schwerpunkt liegt auf der Seite der Liste, die nahe an der gesuchten Nummer liegt.

Wir haben beide Methoden besprochen, um die Indexposition der gegebenen Zahl zu ermitteln.