Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Binäre Suche in sortierten Folgen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 90 Zeilen
- in diesem video geht es um eine sinnvolle anwendung von funktions zeigern im zusammenspiel mit der standard bibliothek nämlich um die
- binäre suche in sortierten folgen zunächst einmal die überlegung wie suche ich eigentlich ein element in einem
- beliebigen und in der regel benutzt man einen solchen algorithmus man hat also hier jetzt mal so eine funktion suche element die bekommt jetzt mal hier ein
- integrer als zeiger übergeben die anzahl der elemente und das element was wir suchen und es wird das durchlaufen und wenn das aktuelle element dem such
- element entspricht dann gehen wir anzeige auf dieses element zurück ansonsten gut statt rey in eckigen klammern adresse operator könnte man
- hier natürlich auch ray plus sie einfach schreiben ok aber was wir im grunde machen dass wir laufen durch das ding durch und das
- nennt man eine sequenzielle suche heute suchen die folge also von vorne bis hinten und wenn wir das element gefunden haben dann ist gut und wenn wir
- es nicht finden dann sind wir im grunde die ganze folge durchlaufen das heißt wir brauchen maximalen sucht schritte wenn die folge ein elemente
- enthält und das funktioniert auch bei unsortierten folgen das ist im grunde immer der weg mit dem man so eine suche
- folge durchsucht also hier unten habe zum beispiel das sind ein paar zahlen auf gelistet und wir suchen jetzt mal die zahl 78 und gehe jetzt schritt für
- schritt durch und das haben wir 78 gefunden und sind glücklich wir haben also das element im best case haben wir einen schritt nämlich wenn das erste
- element und das ist was wir suchen und im worst case wenn wir es gar nicht finden dann sind wir die ganze liste durchlaufen
- ok also dass die sequenzielle suche und die es so wie sie jetzt ist auch im grunde optimal jetzt schauen wir das ganze mal einer an
- für sortierte folgen also wir haben eine sortierte folge und wir suchen einen bestimmten eintrag ja also nehmen wir mal an wir haben eine liste von namen
- die sind dann schon sollten tradierter fondswerte ihnen ist klaus michael dean peter huth sabine sebastian tom ja die sind also schon alphabetisch sortiert
- und wir suchen jetzt einen bestimmten namen in einer solchen sortierten liste und jetzt ist sind sie gefragt überlegen sie mal wie könnte denn so ein
- algorithmus eigentlich aussehen mit dem ich in einem sortierten fällt etwas suche wie viele schritte brauche ich mindestens oder maximal um ein element
- zu finden und wie könnte das ganze dann in cee aussehen also denken sie mal darüber nach reflektieren sie mal und dann gibt es gleich die auflösung
- ok schauen uns das ganze mal also so sieht der algorithmus aus für die sogenannte binäre suche bei sortierten folgen also wir beginnen in
- der mitte des feldes und gucken zunächst einmal ist es eigentlich das element wasser gesucht haben wenn ja super dann sind wir direkt fertig einschritt und
- klasse ja also das ist auch das minimum wir brauchen mindestens diesen einschritt wenn das getestete element kleiner ist als der suche element dann
- weiß ich ja dass alle elemente die links davon stehen noch kleiner sind also passt das nicht also muss ich rechts weiter suchen und im umgekehrten fall
- links und auf diese weise fahre ich in der mitte dann dann vor ort in der mitte der rechten oder der linken hälfte so lange bis sich das element gefunden habe
- oder ich eben festgestellt hat das element ist gar nicht in der liste und das funktioniert auch wirklich nur bei sortierten folgen ja also hier
- nochmal das beispiel wir suchen den eintrag mit der nummer 78 und gucken mal in der mitte und finden die 50 wo die 50 ist es offensichtlich nicht
- ich weiß aber dass alle elemente die links von der 50 stehen jetzt kleiner sind als diese 78 also interessiert mich interessieren mich alle zahlen links von
- der 50 nicht mehr das heißt ich kann die hälfte der zahlen weglassen ich musste mir gar nicht erst angucken weil ich mich auf die sortierung verlasse dann
- gucke ich in der hälfte rechts weiter 83 83 ist zu groß alle elemente rechts der 83 sind größer also kann ich die auch weglassen das heißt ich kann hier ein
- viertel der zahlen weglassen also ich die nächste hälfte 61 61 zu klein und dann gehe ich hier hin und habe die
- 78 getroffen und dieses vorgehen ist genau das was sie vielleicht nutzen würden wenn sie jemand fragen würde eine zahl zwischen 1
- und 100 zu raten ja dann würden sie auch so ungefähr vorgehen ja dann sagen sie 50 und der andere sagt größer und dann würden sie jetzt nicht als nächstes 25
- sagen denn sie wissen alle zahlen keiner 50 sind raus also best case über direct fertig und im worst case brauchen wir sogar it muss von enzo
- basis zwei schritte +1 für den zusätzlichen schritt am anfang also das ist der worst case und man sagt auch dieser algorithmus hat eine
- logarithmische komplexität da ist also wesentlich effizienter als die suche sequenzielle suche in einer unsortierten folge anders formuliert wenn man etwas
- sucht lohnt es sich doch sehr wenn die folge bereits sortiert ist ja so die gute nachricht ist für die binäre suche in einer beiz sortierten einem bereits
- sortierten gibt es tatsächlich eine cd funktion und die heißt research sie kommt aus der stadtbibliothek die liefert uns einen zeiger zurück auf das
- element was gefunden wurde und dann hat die verschiedene parameter ja die hat also ein kino und ein basecap ist ein zeiger auf das element was ich
- suche base ist ein zeiger auf das ray also auf das erste element in dem rey und das eda muss aufsteigen sortiert sein also das ist eine voraussetzung
- aufsteigend heißt der wert wird größer nur 125 87 12 58 13 das ist auch mal aufsteigen und 13 852 eines wäre absteigend endes die anzahl der elemente
- und es ist die größe eines einzelnen elements in dem feld und cmp ist jetzt ein funktions zeiger der zwei versteht er zwei parameter bekommt a und b und c
- mps eine funktion die jetzt zwei werte vergleicht und die gibt uns dann einen wert kleiner 0 zurück wenn a vorgehen der ordnung folgt und größer null wenn a
- nach b in der ordnung folgt sind gleich null wenn das objekt gefunden wurde das ist genau das was uns auch die string
- funktion str cmp 42 strings zurückgibt das ist also eine funktion die eine die zwei elemente a und b ordnet also entweder sagt die sind gleich oder
- dieses liegen unterschiedliche in der ordnung und was man hier sieht ist dass dieser funktion wie serge nur mit momentan arbeitet also mit und visierten
- pointern der funktion ist also völlig egal was in dem murray drin steht das müssen sie zuerst betrachten dieser cmp funktion und was die allerdings braucht
- ist die größe eines elements um in diesen dann navigieren zu können ok also die funktion research implementiert das allgemeine vorgehen
- der binären suche der konkrete inhalt des arrays ist der funktion egal das betrachtet sie gar nicht denn sobald zwei elemente verglichen werden sollen
- wird die cmp funktionen die sie dann übergeben haben aufgerufen das heißt die funktion ist unabhängig vom konkreten datentyp dämmere
- gespeichert ist nur ich muss die größe angeben und ich muss die anzahl der elemente angeben also schauen wir uns das mal ganz
- konkret an wir haben also ein hier mal beispielhaft eine rey mit vier integer werten das soll durchsucht werden und aus sicht des algorithmus ist das
- ganze völlig anonym da sind einfach irgendwelche speicherzellen denn wie gesagt wie serge interessiert sich nicht für den
- konkreten daten trieb so jetzt gebe ich im zweiten parameter zunächst einmal den anfang des base anja das heißt die funktion weiß jetzt aber bei dieser
- speicher stelle fängt das an und die größe eines elements wird ebenfalls übergeben und damit hat die funktion die möglichkeit zwischen elementen zu
- springen ohne die konkret zu kennen wenn es auch nur die größe eines elements und dann haben wir als letzten parameter noch die anzahl der elemente das heißt
- die funktion wie serge weiß jetzt wo ein einzelnes evo das ganze ray endet was in den zellen drin steht ist der funktion allerdings vollkommen egal
- ja und jetzt ist natürlich erforderlich zwei elemente zu vergleich vergleichen und entscheiden welches in der gesuchten ordnung vor dem anderen steht ja und der
- ist natürlich abhängig vom 3 es macht also einen großen unterschied durchsetzen in dreien stecke oder ein element aus einer kundendatenbank da
- gibt es dann eben keine allgemeine funktionalität und stattdessen muss der benutzer die benutzerinnen bzw genauer der aufruf von be said selbst
- eine funktion schreiben und über geben die diesen vergleich vor nimmt und diese funktion wird als funktions zeiger an wie serge übergeben
- ja und da gibt es halt natürlich eine notwendige vereinbarung nämlich dass diese funktion eben zurückgeben muss in welcher beziehung diese zwei elemente
- zueinander stehen also sind die gleich dann wird gleich null zurückgegeben und ansonsten entweder kleiner 0 oder größter nur je nachdem ob 1 vor oder
- nach dem element zwei vorkommt ja und die beiden parameter werden dann als wort übergeben und müssen erst mal auf den 1
- den eigentlichen typ dann gewandelt werden denn weiger kann ich nicht differenzieren ich brauche die tatsächlichen inhalt
- ja und wie serge ruft dann diese funktion mit jeweils zwei parametern auf dem feld aus und verfährt an gemäß den algorithmen entsprechend algorithmus ja
- das ist auch ein das ist ja auch so eine software design pattern zu sagen ich implementiere jetzt diesen den algorithmus allgemein das
- macht wird und für den konkreten fall muss dann halt der benutzer das entsprechend übergeben ok jetzt schauen wir das mal an also so
- sieht eine kompassfunktion aus die bekommt ein wort zeiger pa und die bekommt ein zeiger pb beide konstant und liefert dann eben zurück wenn der wert
- bei pa größer ist als der wert bei plus 1 im umgekehrten fall - einzeln wenn die werte identisch sind dann 0 so jetzt gucken uns das ganze mal für in
- tanja für den fall dass hierbei bis ein integrer sortiert werden sollte dann muss ich zunächst einmal diese zeiger carsten etwas was sich die referenzieren
- kann dh ich war dann in ein insider und pw in einen ebenfalls in ein insider denn ich kann pe und pp nicht
- differenzieren jetzt habe ich in zeiger und die kann ich aber differenzieren und mir angucken was der jeweils steht also wenn der referenziert größer ist als der
- refinanziert dann gebe ich + 1 zurück im umgekehrten fall -1 und wenn die identisch sind das ist dann der 12 dann wird entsprechend 0 zurückgegeben
- ja und das ist genau das was wir haben ja es kann also sein dass mit einem algorithmus hier mal element 1 dass der ph mit element pp verglichen wird
- ok also hier haben wir diesen fall hier habe diese compare funktion die wir gerade schon hatten und hier haben wir jetzt ein dazu gehöriges hauptprogramm
- also wird ein aufgestellt mit integrieren das ist also bereits sortiert aufsteigend und haben eine gewisse
- anzahl gegeben also dass die anzahl der elemente errechnet dass es dann entsprechend acht ja genau die größe von art dividiert durch die größe eines ins
- hier wie gesagt noch mal der hinweis das funktioniert nur wenn ich das gerät hat sich auf diese art definiert dann habe ich hier mein such element das
- eine variable search gespeichert 47 und jetzt wird hier wie serge entsprechend aufgerufen und ihre aufgabe besteht jetzt darin sich zu überlegen wie werden
- denn jetzt hier die parameter definiert und nach dem aufruf gucken wir uns das eben an ist das ergebnis dann wurde das nicht gefunden und
- ansonsten sagen wir der wert wurde gefunden und gehen dass hier entsprechend aus also überlegen sie sich mal kurz die lösung und dann gibt es
- gleich entsprechen die musterlösung okay dann werden wir mal einen blick auf die musterlösung also be search bekommen
- zunächst einmal ein zeiger auf das erste element ja das wir steht hier adresse apparat research dann ein zeiger auf das erste element in den raid kann man
- einfach abschreiben oder und a in eckigen klammern 0 wäre auch möglich dann hier die anzahl an die größe eines einzelnen elements heißt in tja und dann
- braucht diese funktion noch die compare funktion und übergeben wir hier einfach ganz normal mit compare das problem braucht man halt aus also hier haben wir
- den code ich gucke mal direkt an ein hier an der stelle und jetzt müsste ich noch die navas haben hier konflikt den teig genau da
- fehlt einfach noch die standard bibliothek ist in delitzsch so und jetzt fühlen wir das mal aus und wir sehen nicht gefunden im fall von 47 das
- befindet sich jetzt nicht da drin aber wenn ich beiße 7 1 gäbe dann wird das gefunden 43 23 wird auch gefunden und minus fünf
- wird nicht gefunden ja und hier habe ich eben ein sehr sehr effizienten such algorithmus der aber wie gesagt voraussetzt dass dieses
- eingegebene ray entsprechend schon sortiert ist und dass sich eine kompassfunktion mit schicke hier als parameter die dann den vergleich
- durchführt weil wie gesagt die search implementiert den allgemeinen algorithmus den vergleich musste er aufrufe mitliefern
Zum Nachlesen
Binäre SucheDie binäre Suche ist ein Algorithmus, der in einem Array sehr effizient ein gesuchtes Element entweder findet oder dessen Vorhandensein zuverlässig …
Lineare SucheLineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt.
Binärer SuchbaumIn der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt …
SuchbaumIn der Informatik ist ein Suchbaum eine abstrakte Datenstruktur, bei der die Menge von Elementen, in der gesucht werden soll, in einer Baumstruktur …