Die meisten grundlegenden Array – Python

1. Einführung: Hallo zusammen. Willkommen zu diesem Kurs über die meisten grundlegenden Algorithmen. In diesem Kurs erhalten Sie praktische Lektionen zur Implementierung einiger der grundlegendsten Algorithmen von Grund auf. Wenn Sie neu in der Programmierung sind oder ein erfahrener Programmierer sind, ist dieser Kurs hilfreich. Dies gibt Ihnen die Möglichkeit, zu den Grundlagen zurückzukehren und erneut wie die Grundlagen einiger der grundlegendsten Algorithmen zusammenpassen. Ich unterrichte in sehr einfacher Sprache, ohne Fachjargon. Zuerst wird die Logik auf Papier erklärt, und dann wird das Programm mit dem Tool PyCharm von Grund auf neu entwickelt . Sie benötigen einen Computer mit Internetverbindung. Und zu Anaconda und PyCharm der Software. Bitte nehmen Sie die Fersenbeinlänge für den Installationsvorgang. Sie sollten bereit sein , Programme in der PyCharm-Umgebung zu schreiben und auszuführen . Bevor Sie mit diesem Kurs beginnen. Am Ende beherrschen Sie diese grundlegenden Algorithmen und neue Programmierer werden Lust auf mehr Programmierung entwickeln . Danach folgen Lektionen zu einigen der grundlegendsten Algorithmen und die Implementierung von Grund auf neu. Hören hat einige einfache Manipulationen als Warm-up. Lektion 3.4 befasst sich mit binärer Suche und Partitionierung, sehr grundlegenden Algorithmen, wie Sie wissen. Schließlich haben wir bei weniger als fünf ein Klassenprojekt zur Implementierung des Quicksort-Algorithmus von Grund auf neu. Das ist alles. Ich freue mich darauf, euch alle dort zu sehen. 2. Array: Hallo zusammen. In dieser Lektion lernen wir einen sehr grundlegenden Datentyp , der mehrere Objekte zusammen speichern kann. Dies wird als Array bezeichnet. Ein Array ist ein Satz von Objekten nebeneinander im Computerspeicher gespeichert werden. In unserer Diskussion werden wir ganzzahlige Zahlen als Objekte nehmen. Nehmen wir ein Beispiel. Ist ein Array, das die Zahlen 289214 minus sechs in Python enthält. Und Array wird auch Liste genannt. Elemente werden nebeneinander im Speicher platziert. Die Position jedes Array-Elements wird als Index bezeichnet. Der Index beginnt bei Null. Das bedeutet, dass der Index des ersten Elements Null ist. Der Index des zweiten Elements ist eins, der Index des dritten Elements ist zwei usw. Auf diese Weise ist der Index des letzten Elements um eins kleiner als die Gesamtlänge des Arrays. In dem angegebenen Array gibt es also fünf Elemente und die Indizes sind 01234. Mal sehen, wie wir auf jedes Element eines bestimmten Arrays zugreifen und die Zahlen drucken können . In Python. Druckfunktion wird zum Drucken verwendet. Druckfunktion kann das gesamte addierte Ergebnis in einem Aufruf dieser Funktion drucken . Das heißt, die Druckfunktion kennt die interne Struktur des Arrays. Um auf jedes Element des Arrays zugreifen zu können, müssen wir das Array mit einer for-Schleife durchqueren. Diese for-loop druckt jedes Element des Arrays. Die nächste for-Schleife durchläuft jeden Index des Arrays und gibt den Wert an diesem Index aus. Diese Schleife durchläuft jeden Index und die entsprechenden Werte gleichzeitig und druckt beide aus. Ich schlage vor, dass Sie mehr über diese beiden Funktionen, range und enumerate, erfahren, da sie beim Schreiben einer Schleife sehr praktisch sind. Als Nächstes implementieren wir einen Algorithmus um die laufende Summe eines Arrays von ganzen Zahlen zu berechnen. Was ist Running Sum? Summe für das Element eines Arrays ist die Summe aller Elemente von Null bis Pi. Nach dem Summieren erhalten wir also das obere Tal als laufende Summe des ursprünglichen Arrays. laufende Summe für das erste Element ist das Element selbst. laufende Summe für das zweite Element ist die Summe der ersten beiden Elemente. laufende Summe für das dritte Element ist die Summe von drei Elementen und so weiter. Wir mögen die Schritte in einfacher Sprache und versuchen Schritt für Schritt zu visualisieren , wie der Algorithmus ausgeführt wird. Versuchen wir, diesen Algorithmus zu visualisieren. Beginne mit einem Zeiger p am zweiten Element von a. Wir haben also einen Zeiger p. Lassen wir ihn auf das zweite Element zeigen, das a ist. Also hier ist p ein Zeiger, das heißt, er enthält den Wert Index des zweiten Elements, welches eins ist. Derzeit ist P also gleich Eins. Jetzt müssen wir den Wert bei p durch die Summe seines Wertes und des vorherigen Werts ersetzen . Das heißt, wir ersetzen acht durch acht plus zwei, was zehn ist. Dann gehen wir einen Schritt vorwärts und machen dasselbe. Das heißt, ersetzen Sie 91 durch 91 plus zehn, was 101 entspricht. Jetzt gehen wir einen Schritt vorwärts. Es spielt den Wert für mit der Summe von 4,101 ab, was 105 entspricht. Und wir machen genauso weiter. Bewegen Sie B also um einen Schritt vorwärts und ersetzen Sie den aktuellen Wert, der minus sechs ist , durch minus sechs plus 105, was 99 ist. Und wir haben das Ende des Arrays erreicht. Also hört der Algorithmus hier auf. Auf diese Weise können wir die laufende Summe eines bestimmten Arrays von Zahlen finden . Beachten Sie, dass wir keine neue LEA erstellt haben , um diese laufende Summe zu finden Wir haben jedes Array-Element durch das entsprechende laufende Element ersetzt . Als nächstes werden wir versuchen, das bei beliebigem umzukehren, das heißt, bei einem Array, sagen wir 289214 minus sechs, werden wir die Reihenfolge der Elemente in diesem Array umkehren. Nach dem Umkehren wird das Array zu minus 6492182. Wählen wir den Algorithmus im Klartext aus. Also setzen wir zuerst zwei Zeiger auf das erste und letzte Element des Arrays, CPS und PE. Wir haben also PAs und PE. Dann müssen wir die Werte von P, S & P tauschen und dann um einen Schritt vorwärts und PE um einen Schritt rückwärts gehen. Das heißt, wir bewegen P, S & P um jeweils einen Schritt aufeinander zu. Und wir müssen diese einstufige Bewegung von jedem machen und die entsprechenden Werte austauschen , bis sie sich kreuzen. Machen wir das Schritt für Schritt und versuchen zu sehen, was tatsächlich passiert. Wir haben also P, S & P an den beiden äußersten Enden. Wir müssen ihre Werte tauschen. Das heißt, wir müssen die Positionen zwei und minus sechs tauschen . Also bringen wir hierher, bringen minus sechs hier her. Dann bewegen wir VS um einen Schritt vorwärts und PE um einen Schritt zurück. Und tausche wieder ihre Werte aus. Wir bewegen Bier und b0. Jetzt zeigen sie auf denselben Ort. Schluchzen hat also keine Wirkung. Im Grunde genommen. Wir können hier aufhören oder wenn wir mit Schritt vier weitermachen wollen, sobald der Vater das kann ich tun und seitdem haben sie sich gekreuzt. Wir hören auf. Auf diese Weise. Wir können die Elemente des Arrays mit zwei Zeigern umkehren . Ich hoffe, Sie kommen auf die Idee hinter diesen Algorithmen. In dieser Lektion haben wir versucht, die Zustände einiger der grundlegenden Algorithmen zu visualisieren . Wir haben noch keinen Python-Code geschrieben. In der nächsten Lektion werden wir echten Code in der Python-Umgebung schreiben und ausführen. Das ist also alles für diese Lektion. 3. Array: Hallo zusammen. In dieser Lektion lernen wir etwas über Partitionierung. Was partitioniert Ellie? Lassen Sie uns das anhand eines Beispiels erklären. Nehmen wir eine LEA mit den folgenden Zahlen. Das ist 387-272-1402 Partition dieses Arrays, wir müssen zuerst eine spezielle Zahl namens Pivot auswählen, die eine der Zahlen ist, die im Array vorhanden sind. Angenommen, wir wählen vier als Pivot-Nummer. Wir müssen die Zahlen im Array neu anordnen. Also, nachdem alle Zahlen links vom Pivot neu angeordnet wurden, oder kleiner oder gleich dem Pivot-Wert. Und alle Zahlen rechts vom Pivot sind größer oder gleich dem Pivot-Wert. Wenn wir SDP vert wählen, könnte eine mögliche Lösung wie auf dem Bildschirm gezeigt sein. Die Lösung ist 032-14-7078. Beachten Sie, dass Zahlen links vom Pivot für weniger als gleich vier stehen. Zahlen rechts von vier, gleich vier. Das linke Subarray und die Beine sind nicht unbedingt von selbst sortiert. Beachten Sie auch, dass, wenn wir das gesamte Array sortiert hätten, nach der Partitionierung die Position, der Pivot dieselbe Position erhält wie die Position, die er nach dem Sortieren des gesamten Arrays erhalten würde . Extrahieren, um einen Algorithmus zur Partitionierung dieses gegebenen LA zu entwickeln Gehen wir den Algorithmus Schritt für Schritt durch. Zuerst müssen wir den Pivot an der ersten Stelle dieses Arrays platzieren . Dann müssen wir zwei Zeiger nehmen, P1 und P2, und sie auf die ersten beiden Elemente zeigen lassen. Also zeigt p1 auf das erste Element und v2 auf das zweite Element. Dann müssen wir P2 Schritt für Schritt bis zum Ende dieser LA verschieben . Und während wir dies verschieben, wir bei jedem Schritt etwas tun, müssen wir bei jedem Schritt etwas tun, das als Checked and Swap bezeichnet wird. Was müssen wir also wie folgt tun? An jeder Position von P2 müssen wir prüfen, ob der Wert bei p2 kleiner oder gleich dem Pivot ist. Wenn nein, dann tu nichts. Aber wenn ja, dann müssen wir den anderen Zeiger p1 um einen Schritt inkrementieren und dann die Werte von P1 tauschen und P2 wird aufhören, wenn P2 das Ende des Arrays erreicht. Lass uns die Schritte ausführen. Derzeit befindet sich P2 also auf Position zwei und sein Wert ist acht. Also ist P2 nicht weniger als für b gearbeitet. Beide sind also in einem Schritt fällig. 77 ist also wieder nicht weniger als gleich vier. Also bewegen wir P2 um einen Schritt. Jetzt ist zwei weniger als der Pivot für. Also müssen wir diesen Unterschritt hier machen. Was wir jetzt tun müssen, ist p1 um einen Schritt vorwärts zu bewegen und dann die Werte von P1 und P2 zu tauschen . Dann bewege P2 erneut um einen Schritt. Und wieder sehen wir, dass der Wert bei P2 , der aktiviert ist, kleiner oder gleich vier ist. Also müssen wir diesen Swap-Schritt erneut durchführen , der zuerst P1 um einen Schritt morph ist. Und dann tausche die Werte von P1 und P2 aus. Bewege P2 erneut um einen Schritt. Und wieder beobachten wir, dass der Wert bei P2 , der drei ist, kleiner oder gleich vier ist. Also bewegen wir p1 erneut um einen Schritt und machen dann den Tausch. Mehr 321 Schritte. Und wir sehen, dass Null wieder kleiner als vier ist. Also bewegen wir uns eins nach dem anderen und machen dann den Tausch. Zu diesem Zeitpunkt befindet sich P2 am Ende dieses Arrays. Die Schleife über P2 ist also beendet. Als letzten Schritt müssen wir nun die erste Position des Arrays, das ist der Pivot-Wert , mit p1 austauschen . Dadurch wird der Pivot an die richtige sortierte Position gebracht. Und jetzt sehen wir, dass alle Zahlen links vom Pivot oder kleiner als vier sind. Und alle Zahlen rechts vom Pivot sind größer als gleich dem Pivot-Wert für. Dies ist eine gültige Partition des Arrays. Ich hoffe, dies hat dazu beigetragen, die internen Schritte beim Erlernen des Algorithmus zu visualisieren . Als Nächstes gehen wir den Python-Code für diesen Partitionsalgorithmus durch . Hier ist eine Python-Funktion namens partition, die eine Eingabe namens a, die Danny ist, entgegennimmt und sie in Bezug auf einen Pivot partitioniert. Und dies setzt voraus, dass sich der Pivot an der ersten Position dieses Arrays befindet. Gehen wir diesen Algorithmus Zeile für Zeile durch. Zuerst initialisieren Sie die beiden Zeiger p1 und p2 auf 0,1. Dann setzen wir den Pivot, indem wir die erste Position des Arrays lesen , die eine Null ist. Dann schauen wir uns, wie bereits erwähnt, gerne P2 an. Also bewegt sich P2 von seinem aktuellen Standort bis zum Ende des Arrays. Das Ende des Arrays wird durch die Länge des Arrays gekennzeichnet. Dann implementieren wir mit der nächsten if-Anweisung die Logik , die wir zuvor besprochen haben. Das heißt, wenn a von p2 kleiner als gleich Pivot ist, dann bewegen wir p1 und tauschen dann die Werte von P1 und P2 aus. Diese Zeile AFP ein Komma f p2 ist gleich einem f B2 Komma f von p1 ist der Python-Ausdruck zum Austauschen von zwei Werten. Hier sind die Werte a von P1 und P2. Das ist also eine sehr intuitive Syntax. Und dann beginnen wir diese if-Anweisung, wir bewegen P2 weiter, naja, einen Schritt in jeder Iteration dieser While-Schleife. Und wenn sie aus der While-Schleife kommen, das heißt, wenn P2 das Ende des Arrays erreicht, tauschen wir wieder Null und a von P1 aus. Dies dient dazu, den Pivot von seiner aktuellen Position, dem Anfang des Arrays, an seine endgültige Position zu bringen. Und das ist alles für diese Lektion. 4. Array: Hallo zusammen. In dieser Lektion führen wir das Python-Programm für die Array-Partitionierung aus. Hier haben wir die Partitionsfunktion , die ich bereits gesehen habe. Außerdem gibt es eine Hauptfunktion , die eine Liste namens my list erstellt und die Partitionsfunktion mit meiner Liste als Eingabe aufruft . Lassen Sie uns das Programm im Debug-Modus ausführen. Setzen wir einen Breakpoint in die Hauptfunktion und führen ihn aus. Wir sind also am Breakpoint. Und lass uns zuerst die Liste erstellen, meine Liste. Bitte behalten Sie diesen Variablenbereich im Auge und Sie können die Werte der Variablen sehen. Und dann geben Sie die Partitionsfunktion ein. Initialisieren Sie zuerst p1 und p2, die beiden Zeiger. Und dann setzen Sie den Pivot, dem wir annehmen, dass das erste Element des Eingabe-Arrays ist. Also hier ist der Drehpunkt vier. Lass uns die Schleife über P2 betreten. P2 bewegt sich also von seiner aktuellen Position zum Ende des Arrays. Erstens, wenn P2 acht ist, was nicht weniger als der vierten Periode entspricht. Also gehen wir über die if-Anweisung hinaus und gehen zur nächsten Iteration der Schleife über. Nun, wenn P2 gleich 77 ist, ist das nicht weniger als gleich dem Drehpunkt. Also fahren wir mit der nächsten Iteration fort. Wenn nun P2 zwei ist, ist das weniger als gleich dem Pivot Vier. Also gehen wir in die if-Anweisung, inkrementieren darüber hinaus um u1 und machen den Tausch. Wir gehen zur nächsten Iteration über. Jetzt ist AF P2 eingeschaltet. Geben Sie also erneut die if-Anweisung ein und machen Sie den Tausch. In der nächsten Iteration ist P2 drei, was weniger als gleich Pivot vier ist. Also wieder geben wir die if-Anweisung ein und führen den Tausch durch. In der nächsten Iteration. Wenn B2 Null ist, was kleiner als p ist, wofür? Also geben wir die if-Anweisung ein und führen den Tausch erneut durch. Und jetzt hat P2 das Ende des Arrays erreicht. Also kommen wir aus der ganzen Schleife raus. Und dann machen wir den letzten Tausch, den Pivot-Wert, der sich an der ersten Stelle mit b1 befindet. Und das vervollständigt den Algorithmus. Nicht im Variablen-Bereich. Sie können den aktuellen Stand der Mindlist sehen. Und es wurde partitioniert. Also alle Zahlen links von vier oder weniger als gleich vier, und alle Zahlen rechts von vier oder größer als gleich vier. Wenn ich also den gesamten Algorithmus in einer sehr einfachen Sprache erklären muss, wäre es so. Es gibt zwei Zeiger, p1 und p2. Was machen sie wirklich? B1 behält eine Grenze zwischen den beiden Partitionen bei. Die linke Partition, die vom Anfang des Arrays bis zu p1 reicht, ist die Menge von Zahlen, die kleiner als gleich dem Pivot-Wert sind . Und die Zahlen rechts von P1 sind die Zahlen, die größer als gleich dem Pivot-Wert sind. Wie erreichen p1 und p2 das? B2 explodiert jede neue Zahl des Arrays. Und wenn diese neu erforschte Zahl kleiner als gleich dem Pivot-Wert ist, erweitert B1 die linke Grenze und diese neue Zahl wird in die linke Partition verschoben. Durch Tauschen. Auf diese Weise die linke Partition immer enthält die linke Partition immer Werte, die kleiner als gleich dem Pivot sind. Und die rechte Partition enthält Werte, die größer als gleich dem Pivot-Wert sind . Beachten Sie, dass die rechte Partition nach T1 beginnt und sich bis P2 erstreckt. Ich schlage vor, dass Sie dieses Programm in Ihrer Python-Programmierumgebung durchlaufen . Damit Ihnen die internen Schritte sehr klar werden. Und das ist alles für diese Lektion. 5. Binärsuche: Hallo zusammen. In dieser Lektion lernen wir etwas über die binäre Suche. Was ist binäre Suche? Hier? Wir erhalten ein sortiertes Array von ganzzahligen Zahlen, und wir erhalten auch eine andere einzelne Ganzzahl x, wir müssen die Position von x in diesem sortierten Array a finden. Wenn x in a nicht vorhanden ist, können wir minus eins zurückgeben. Nehmen wir ein Beispiel. Wir erhalten das sortierte Array a, das heißt, Sie können sehen, dass es in aufsteigender Reihenfolge sortiert ist. Und wir bekommen auch eine andere Zahl x. Wir müssen die Position von x finden. Wenn x in a vorhanden ist, müssen wir andernfalls minus eins zurückgeben. Hier können wir also sehen, dass sieben in der LEA vorhanden sind. Und der Standort von sieben ist Index vier. Das bedeutet den fünften Platz. Also müssen wir vier zurückgeben. In diesem Fall. Wenn der Wert von x ist, dann können wir sehen, dass neun im gegebenen a nicht vorhanden ist. Die binäre Suche sollte also minus eins zurückgeben. Versuchen wir, den binären Suchalgorithmus zu visualisieren. Wir erhalten das sortierte Array, das in aufsteigender Reihenfolge sortiert wird. Und wir müssen nach einer bestimmten Zahl X in a suchen. Hier ist der Wert von x sieben, also müssen wir nach sieben suchen. Beachten Sie zunächst, dass wir das gesamte Array ein Element nach dem anderen durchqueren und nach x suchen können . Dies erfordert n Schritte, wobei n die Gesamtzahl der Elemente im Array ist. Wenn das Array zu lang ist, die Zeit, die für eine Suche auf diese Weise benötigt wird, ebenfalls sehr lang. Das ist also kein effizienter Weg. Wenn das Array nicht sortiert wurde, müssen wir das so machen. Aber im Moment ist das Array sortiert. Also müssen wir diese Eigenschaft nutzen, um unseren Algorithmus zu beschleunigen. Schreiben wir den Algorithmus in einfacher Sprache. Zuerst müssen wir zwei Punkte am Anfang und Ende des Arrays setzen . Sagen wir die LPS und p. Wir sagten, P steht am Anfang und p am Ende. Als nächstes finden wir den Mittelpunkt von P S & P. Das heißt, wir finden P S plus p, alle geteilt durch zwei und unten gerundet. Das wird also der Mittelpunkt genannt. Beachten Sie, dass dies voreingenommen ist. Das heißt sicher P S ist zwei und p ist drei. Dann ist Mate zwei plus 3/2. Und diese Division ist eine Integer-Division. Das Ergebnis ist also zwei. Der Mittelpunkt von 2,3 ist zwei, Mittelpunkt von 23,4 ist drei. Der Mittelpunkt von 234,5 ist drei. Deshalb heißt es links voreingenommen gemacht. Lassen Sie uns die Mitte des aktuellen P S & P berechnen. P S ist Null und P ist 70 plus sieben mal zwei, was 3,5 entspricht. Abgerundet. Hallo ist drei ist gleich drei. Mitte wird also bei Index drei platziert. Jetzt suchen wir nach x. Also vergleichen wir den Wert an mir mit x. Wenn x gleich Mate ist haben Sie die Position von x gefunden, und wir geben den Wert von Fleisch zurück. Wenn nicht, dann steht x entweder rechts von Fleisch oder links von Fleisch. Wenn x größer als Fleisch ist, dann steht x rechts von Fleisch. Und in diesem Fall können wir das umgehen, was sich links vom Fleisch befindet , damit wir das gesamte Subarray, das Starttreffen, wegwerfen können . Auf diese Weise können wir den Suchraum sehr schnell reduzieren. In jeder Iteration kann also die Hälfte des gesamten Arrays verworfen werden. Und das macht diese binäre Suche sehr schnell. Jetzt ist x größer als drei. Also bewegen wir PS. Treffen Sie plus eins. Das heißt, das direkt rechts vom vorherigen gemacht wurde. Jetzt wissen wir, dass alles, was links von Gleichaltrigen übrig ist, verworfen werden kann. Wir haben unseren Suchraum um die Hälfte reduziert. Jetzt. Berechne mich noch einmal. Derzeit ist PACs vier und p ist sieben. Das Fleisch von 4,7 ist also 5,5. Unten sind fünf abgerundet. Treffen wir uns also um fünf Uhr. Jetzt ist der Wert des Wertes bei Fleisch 88 nicht gleich x. Und wir sehen, dass jetzt x kleiner ist als Mate. Also bewegen wir B, um minus eins zu machen. Jetzt, in der nächsten Iteration, berechnen wir erneut die Mitte. Sie werden also sehen, da PAs und PE den gleichen Wert haben, auch der Wert von Fleisch derselbe. Also werden wir wieder auf denselben Ort zeigen. Jetzt. X ist gleich meet found x. Und wir sind zurückgekehrt, gemacht. Auf diese Weise. Wir können die Position von x in den sortierten Daten finden. Nehmen wir nun ein anderes Beispiel , bei dem x in der LA nicht vorhanden ist, sagen wir x gleich neun. Auch hier beginnen wir am Anfang mit PAS. Und am Ende. Die Mitte zeigt auf den Mittelpunkt. Wir vergleichen den Wert bei , der drei ist, mit x, x ist neun. Also muss x rechts von Fleisch sein. Also bewegen wir VS, um uns plus eins zu treffen. Und wieder rechnen wir, was hier ist. Wir vergleichen den Wert x mit x. Der Wert von x ist neun, also ist neun größer als acht. X muss also das Licht des Fleisches sein. Also verschieben wir PAs auf Mitte plus eins. Jetzt rechnen wir uns wieder, das heißt, was genauso sein wird wie bs. Wir vergleichen x mit Nate und stellen fest, dass x jetzt weniger als Fleisch ist. Also bewegen wir B auf Mitte minus eins. Sie in diesem Stadium, Beachten Sie in diesem Stadium, dass P S & P sich kreuzen. Also halten wir an und kehren minus eins zurück. Das bedeutet, dass X in diesem Fall in diesem sortierten Array nicht vorhanden ist. Schauen wir uns den Python-Code für die binäre Suchfunktion an. Die Funktion akzeptiert zwei Argumente. Das erste ist das Array, ist ein Array von ganzen Zahlen, die in aufsteigender Reihenfolge sortiert sind. Und x ist eine weitere Ganzzahl. Wir müssen die Position von x in a finden. Und wenn x nicht vorhanden ist, geben wir minus eins zurück. Gehen wir die Funktion Zeile für Zeile durch. Zuerst initialisieren wir P, S & P, die Start- und Endzeiger. Also ist p, wird auf Null initialisiert, oder der Index der Position ganz links. Und PE ist gleich der Länge von minus eins. Das ist der Index des Standorts ganz rechts. Dann starten wir die While-Schleife mit der Bedingung P S ist kleiner als gleich p. Das heißt, wir fahren mit der While-Schleife fort. Die beiden Zeiger kreuzen sich nicht. Zuerst berechnen wir den Partner, der , wie wir zuvor erklärt haben, das linksvoreingenommene Treffen ist. Und dann prüfen wir, ob x gleich a von mid ist. Das bedeutet eine Wertschätzung. Wenn a von mid gleich x ist, dann haben wir x gefunden und geben die Position zurück , die erstellt wurde. Wenn nicht, dann verwerfen wir je nachdem, ob x größer als a ist oder x weniger als eine Hälfte gemacht ist, x größer als a ist oder x weniger als eine Hälfte gemacht ist, die Hälfte des Arrays. Wenn also x größer als a von mid ist, verwerfen wir die linke Hälfte des Arrays und den Wert selbst. Das heißt, wir setzen auf Mitte plus eins. Wenn x kleiner als m ist es. Dann verwerfen wir den rechten Teil des Arrays und setzen p auf Mitte minus eins. Und dann wieder berechnen wir die Übereinstimmung mit diesen aktualisierten Standorten von P S & P. Und wir wiederholen diesen Weg. In jeder Iteration verwerfen wir also die Hälfte des Arrays. Am Ende können also zwei Dinge passieren. Entweder wird X gefunden und in diesem Fall geben wir die entsprechende Position von X zurück oder X wird nicht gefunden. Und P, S & P kreuzen einander. Und wir kommen während der Schleife heraus und kehren minus eins zurück. In diesem Fall. Ich hoffe, Sie bekommen die Grundidee wie dieser binäre Suchalgorithmus funktioniert. Das ist alles für diese Lektion. 6. Python-Programm mit binärer Suche: Hallo zusammen. In dieser Lektion lernen Sie das Python-Programm für die binäre Suche kennen. Hier ist die binäre Suchfunktion, die Sie bereits gesehen haben. Außerdem haben wir eine Hauptfunktion geschrieben , die die binäre Suche aufruft. Setzen wir also einen Breakpoint in die Hauptfunktion und führen ihn aus. Wir sind also am Breakpoint. Also erstellen wir zuerst ein Array, das bereits sortiert ist. Wie du siehst. Bitte behalten Sie den Variablenbereich im Auge, in dem Sie die aktuellen Werte der Variablen sehen können. Wir definieren x bis sieben. Und dann rufen wir binäre Suchfunktion mit a und x als Eingaben auf. Wir wollen die Position von X in einem finden. Geben wir also die binäre Suchfunktion ein. Zuerst P, S&P. Die Start- und Endzeiger wurden auf 0,7 initialisiert, wie Sie im Variablenabschnitt sehen werden. Dann betreten wir die ganze Schleife mit der Bedingung P ist kleiner als gleich p. Dann berechnen wir den mittleren Wert des Mediums ist drei. Und dann prüfen wir, ob x gleich oder kleiner als, gleich oder kleiner oder größer als Fleisch ist. Beachten Sie, dass, wenn wir x mit Fleisch vergleichen, wir wirklich den Wert an Punkt a von mid meinen, wenn er gleich ist, um ihn zu erfüllen, und wir ihn bereits gefunden haben, und die Funktion kehrt zurück. Aber wenn nicht, wird es zurückgesetzt. Entweder p ist RPE, abhängig davon, ob x größer oder kleiner als ist. Lass uns sehen. Also hier ist der Wert von x, wie wir wissen, sieben, und a von mid ist drei. Also ist x nicht gleich x ist größer als eine Hälfte. Also setzen wir den Zeiger ps zurück, um plus eins zu machen. In diesem Schritt verwerfen Sie die Hälfte davon. Fahren Sie also mit der nächsten Iteration fort. Mit den neuen Werten von P S&P. Der neue Wert von P, S ist vier und p ist sieben. Also schauen wir uns jetzt das Subarray an, beginnend am Fehlerort und bis zu diesem bestimmten Ort berechnen wir Treffen wieder. Der Wert von Fleisch ist jetzt fünf und entspricht acht. Derzeit ist es also weniger als Mitte. Also kommt es her. Und jetzt setzen wir p0 auf Mitte minus eins. Schauen Sie sich nun die Variablen an. Abschnitt P, BE und PAs haben den gleichen Wert, der vier ist. Also der Punkt auf dieselbe Stelle im Array. Wir berechnen Mitte. Mid ist auch für offensichtlich. Jetzt ist x gleich f meet. Und wir geben Mitte zurück, was dem Wert vier entspricht. Wir sind also von der binären Suchfunktion zurückgekehrt und das Ergebnis ist vier. Das bedeutet, dass X bei Index vier des sortierten Arrays vorhanden ist . Ändern wir X, 7-9. Und dann noch einmal Schritt durch dieses Programm. Wir haben die gleiche LEA, die bereits sortiert ist. Wir setzen x auf neun und geben dann die binäre Suche ein. Also werden P, S & P initialisiert. Starte die Schleife. Der Wert von Fleisch liegt zunächst bei drei. Also ist x nicht gleich x ist größer als m, Es ist ein bs plus eins. Und fahren Sie mit der nächsten Iteration fort. Und jetzt ist MIT fünf. AF made ist also nicht gleich x, ist kleiner als x. Also setzen wir jetzt ps zurück, um Handschuhe anzuziehen und mit der nächsten Iteration fortzufahren. Rechnen Sie sich erneut, das sind sechs. Also traf AF jetzt seine Entscheidung, die nicht gleich x ist. Nein, x ist kleiner als a von Mitte. Komm auf jeden Fall her und mache einen Reset p minus eins. Beachten Sie nun, dass der Wert von P, S sechs und der Wert von B fünf ist. Das heißt, P, S & P haben sich gekreuzt. Hier bricht die ganze Schleife und wir kehren minus eins zurück. Sie werden also sehen, dass das Ergebnis minus eins ist. In diesem Fall wird der Wert von x nicht im sortierten Array gefunden, daher wird minus eins zurückgegeben. Ich schlage vor, dass Sie diese binäre Suchfunktion in Ihrer Python-Entwicklungsumgebung durchlaufen Ihrer Python-Entwicklungsumgebung , damit Sie sich mit den internen Schritten vertraut machen. Und nenne diese Funktion mit verschiedenen sortierten Arrays mit unterschiedlichen Längen. Machen Sie sich daher mit der internen Funktionsweise dieses Algorithmus vertraut . Das ist alles für diese Lektion.