Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Binäre Suche anschaulich erklärt - mit Übungen [deutsch]
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 139 Zeilen
- heute beschäftigen wir uns mit der binären suche nachdem er in der letzten folge die relativ einfache aber doch ineffiziente lineare suche
- abgefrühstückt haben die habe ich ein gutes spiel entdeckt auf scratch ob die rolle eingeblendet dieser roboter errät eine zahl die wir uns denken nicht
- demonstriert mal kürzer sagt denkt der eine zahl zwischen null und 100 habe ich mir gedacht ich habe mir die 72 gedacht sagt da ist die zahl 50 oder mehr muss
- ich sagen jetzt denkt danach und sagt ist 75 oder man ja nein 72 ist nicht 75 oder mehr sondern weniger also sage ich nein er sagte ist 72 62 oder mir ja ja
- ist es ist 68 oder mehr 72 haben wir gesagt 71 oder klar 73 oder mehr nein 72 oder mehr ja er hat die zahl erraten und da hat
- dafür sieben schritte gebraucht falls sie planen dieses video zur unterhaltung zu schauen dann stecken sie es einfach gehen sie zu netflix machen
- sie bisschen italien mit irgendwelchem serien shit falls sie planen die binäre suche zu verstehen dann halten sie jetzt das video an und versuchen sie zu
- rekonstruieren wie der roboter das gemacht hat das ist ein sehr einfaches programm und er benutzt dazu die binäre suche versuchen sie mit ihrem kleinen
- bruder ja kleinen schwester oder ihrem onkel oder ihrer tante dieses spiel zu machen sie gehen hin sagen denk dir eine zahl zwischen null und 100 und dann
- stellen sie ja nein fragen sowie der roboter wenn sie das kapiert haben haben sie drei viertel der mittel bereits
- eingefahren also machen sie es jetzt wahr und ich mit dem roboter auch nochmal spiele
- [Musik] [Musik] ok so einfach kann es gehen jetzt wollen
- wir uns das dings mal bisschen genauer anschauen sie haben bestimmt den trick des roboters herausgefunden erteilt das
- vorhandene zahlenmaterial immer in zwei hälften und überlegt sich wo ist die gesuchte zahl drin das heißt binäre suche binär heißt es gibt nur zwei werte
- 0 und 1 wahr und falsch ist es war das deine zahl in dieser hälfte liegt also 50 oder größer ja das ist in unserem fall weiter 72 klar
- also können wir die zahlen von 1 bis 49 rausschmeißen jetzt bleiben uns die zahlen von 50 bis 100 in der mitte ist die 75 der roboter
- fragt uns also ist deine zahl 75 oder mehr es ist völlig wurscht ob er fragt 75 oder weniger oder 75 oder mehr
- wichtig ist für ihn dass er erfährt in welcher hälfte ist die zahl wir sagen nein sie ist kleiner als 75 das heißt jetzt kann er alle zahlen zwischen 75
- und 100 wegschmeißen und auch die zahlen von null bis 49 da wir am anfang gesagt haben unsere zahl ist 50 oder größer es bleiben die zahlen von 50 bis 74 wenn
- sie hier die variablen ab und laura anschauen was er hier die untere und obere grenze speichert er grenzt also den zahlenraum immer mehr ein
- nun ist die mitte 62,5 in diesem fall ob wir hier abrunden mit 62 arbeiten oder mit 63 ist völlig wurscht er rundet ab sagt es 62 oder mehr ja in
- unserem fall definitiv also haben wir den zahlenraum von 62 bis 74 und wir nähern uns schon an wir suchen wieder die mitte die mitte ist 68 ist eine zahl
- 68 oder mehr ja ist sie in unserem fall wir teilen den verbleibenden zahlenraum wieder in der mitte die mitte ist 71 ist eine zahl 1 70 oder mehr
- also bleiben uns nur noch die zahlen von 71 bis 74 in der mitte steht eigentlich die 72,5 es gibt keine richtige mittel 100 auf 73 wie gesagt wie wir das machen
- werden wir gleich besprechen es verbleiben nur noch die zahlen 1 70 und 72 er sagt uns ist die zahl 72 oder mehr
- wir sagen ja und da ist neben der 72 keine andere zahlen mehr gibt sagt der aha eine zahl ist die 72 hat er ganz schön schlau gemacht da man vielleicht
- noch ganz kurz zu der frage warum teilen wir immer genau in der mitte stellen sie sich vor wir haben die zahlen von eins bis 100
- und da würde uns fragen ist eine zahl größer als 5 und wir sagen höchstwahrscheinlich ja dann hat er nicht viel gewonnen
- in der mitte zu teilen ist am effizientesten verraten was der roboter hier macht ist die binäre suche anzuwenden genauso suchen wir in einem
- nach einzelnen zahlen wir haben eine reihe von 1 bis 100 wir suchen nach einer zahl zum beispiel nach der 97 oder nach der 72 und wollen wissen ist die
- treten genauso suchen wir mit der binären suche oder teilen uns das gerät in zwei hälften schauen in welcher hälfte ist es schmeißen die eine hälfte
- weg und machen mit der anderen hälfte wieder genau weiter wie das genau funktioniert erkläre ich ihnen jetzt aber sie sehen es ist nicht schwierig zu
- kapieren deshalb bin ich getrost dass ihr leben und ihr verständnis wunderbar sein werden
- das freut mich schon so sehen nehmen wir als beispiel mal die sary des sieben elemente unnötig zu bemerken wissen sie bereits dass in den meisten
- anderen programmiersprachen das erste element mit dem index 0 beginnt in scratch beginnen wir mit dem index ein gutes hat sieben elemente und enthält
- sieben zahlen wir wollen jetzt in diesem nach einer zahl suchen und zwar sagen wir mal nach der zahlen neuen wir wollen also wissen ist die zahl neun da drinnen
- was wir können müssen ist erstens den anfang und das ende der liste definieren wir müssen wissen welchen indexwert haben die jetzt am anfang ist man
- relativ einfach dann müssen wir wissen welchen indexwert hat das mittlere element denn wir brauchen ja das mittlere element um den den zahlenraum
- oder unsere liste zu teilen und dann müssen wir natürlich noch prüfen können wo befindet sich der wert befindet dass ich links befindet er sich
- rechts oder befindet er sich in der mitte wenn wir all dies gemacht haben müssen wir das wiederholen daneben wir natürlich eine schleife und zwar so
- lange bis wir unseren gesuchten wert gefunden haben schauen wir erstmal eine einfache aufgabe an wir müssen das anfang und das ende der liste definieren
- ist klar wo fängt die liste an beim indexwert 1 wo hört die liste auf beim indexwert 7 das würden wir in variablen festhalten
- zb index anfang und indexende als nächstes müssen wir wissen welches ist das mittlere element wir als schlaue personen sehen das natürlich sofort das
- ist hier die fio weil links 10 3 und 16 3 wie können wir das mathematisch berechnen ist klar wir holen den index des ersten elements den index des
- letzten elements und teilens durch zwei in unserem beispiel haben wir also 1 pro7 geteilt durch zwei gibt vier wissen wir das vierte element ist unser index
- in der mitte als nächstes müssen wir jetzt prüfen wo sich der gesuchte wert befindet ist unser index in der mitte der gesuchte
- wert dann sind wir fertig also angenommen wir hätten die zehn gesucht dann könnten wir jetzt sagen prima index mitte ist 10 sind wir schon fertig falls
- der wert von index mit größer ist als unser gesuchter wert dann müssen wir links suchen das heißt da 10 größer 9 ist 9 ist der gesuchte wert müssen wir
- in der linken hälfte des race suchen also rio falls der index mit bert kleiner ist als der gesuchte wert müssen wir recht suchen es ja klar
- falls also unser gesuchter wert 22 wäre unsere mitte ist 10 hatten wir zehn müssen dann natürlich recht suchen ganz logisch sie sehen es ist mehr eine frage
- des verständnisses das müssen sie jetzt umsetzen können in dieser ganzen computerei schauen wir uns mal an wie suchen wir ben links was bedeuteten des
- dazu unser index mitte wert ist größer als unser gesuchter wert 10 ist größer als neun das neue indexende und so neues array
- das restaurant in dem wir suchen reicht natürlich vom element 1 bis zum element 3 das ist uns ja völlig klar deinen element 4 bis 7 steckt nicht drin
- wie können wir das mathematisch oder programmierer risch ausdrücken indem wir sagen der neue index ende ist index mit minus 1 wir müssen ja nur von anfang bis
- mitte - 1 suchen entsprechend suchen gerecht sind denn wir sagen der index anfang rutscht über definiert einen neuen anfang des restaurants nämlich
- einst hinter damit index plus 1 ehrlich gesagt finde ich und es gut kapieren kann wenn sie damit
- schwierigkeiten haben besteht natürlich auch die möglichkeit ist einfach auswendig zu lernen aber eigentlich wäre kapieren wahrscheinlich smarter dann
- exerzieren wir diesmal an folgendem beispiel durch versuchen in diesem jahr die zahl neuen des re besteht aus sieben elementen überflüssig zu bemerken dass
- in den meisten anderen programmiersprachen das erste element des rs den indexwert 0 hat aber das wissen sie schon scratch fangen wir mit
- 1 an wir erkennen den index anfang das ist nämlich das erste element des also der erste indexwertes 1 der index am ende
- ist die sieben letztes element des arrays und der index in der mitte ist die vielen ähnlich wert eins plus wert 7 durch zwei gleich vier
- welches ist die erste frage die wir uns stellen wir fragen zuerst ist der mittlere wert identisch
- mit unseren gesuchten wert dann werden wir direkt schon am ziel da aber zehn nicht gleich neun ist müssen wir weitermachen und war es
- überprüfen ist der wert links oder ist er rechts dazu sagen wir ist der wert in der mitte
- größer als unser gesuchter wert ist da was richtig 10 ist größer als neun das bedeutet wir müssen in welchem
- bereich des rs suchen im linken bereich das heißt es bleibt uns nur noch ein rest von element 1 bis
- element drei übrig wie kommen wir rechnerisch auf die 3 wir sagen unseren neues ende ist die mitte - 1 da wir
- links von damit suchen danach machen wir das ganze von vorne wie berechnen wir die neue mitte also
- die mitte in den restlichen eray indem wir suchen wir wissen jetzt die neue mitte ist die zwei nämlich eins plus 3 durch 2 jetzt
- haben wir den bereich in dem die gesuchte zahl steckt eingrenzen können auf den bereich re 1 bis 3 wie gehen wir jetzt weiter vor
- wir fragen ist der wert in der mitte unser gesuchter wert falls das der fall ist sind wir schon fertig und freuen uns falls das nicht der fall ist müssen wir
- was tun wir haben ist der wert in der mitte größer als
- unser gesuchter wert ist das der fall nein denn fünf ist nicht größer als neun in welchem bereich des rs müssen wir jetzt suchen
- klar wir suchen rechts von unserem mittelwert unser index anfang wandert also eins rechts neben die mitte der restliche bereich des arrays indem wir
- jetzt suchen ist natürlich ziemlich kleiner besteht nur noch aus einem element nämlich dem element mit dem indexwert nummer drei die mitte ist also
- nicht schwierig zu finden wir können sie natürlich trotzdem ausrechnen indem wir sagen anfang ist drei ende ist 33 +3 durch zwei gibt drei also ist der
- mittlere indexwert des bereichs leben wir noch suchen können die drei also das element mit der 3 der wert 9 wie machen wir weiter wie
- immer dem computer ist es egal ob das restliche heraus 200 elementen besteht oder aus zwei oder aus einem zuerst fragen mir ist der wert des mittleren
- elements gleich der gesuchten zahl ist da was ja natürlich es ist der berg 9 wir suchen die zahlen 9 also haben wir unsere suche erfolgreich abgeschlossen
- sie haben gesehen dass vorgehen ist eigentlich immer das gleiche zuerst mal definieren wir anfang ende mitte dann schauen wir ob der wert des mittleren
- elements unserem gesuchten wert entspricht wenn das nicht der fall ist schauen wir müssen wir links oder rechts suchen der grenzen des re entsprechend 1
- beziehungsweise den restlichen suchbereich umfang dann wieder von vorne an wir definieren die mitte wir schauen ob
- in der mitte unser gesuchter wert steht falls nicht schauen wir ob unser gesuchter wert links oder rechts der mitte steht entsprechend definierung der
- neuen anfang bzw neues ende als das restaurant dann fangen wir wieder an mir sagen was ist denn die mittel wir schauen ist in
- der mitte der gesuchte wert und so weiter und so fort und irgendwann haben wir s gebunden dem computer ist es egal ob das eine millionen mal macht oder nur
- dreimal wird ist für uns erledigen und den wert binär finden danke lieber computer jetzt brauchen wir das nur noch schön programmierer technischem struktur
- gramm umgesetzt ich zeige ihnen struktur gramm das erstmals erwischt aussieht sehr sehr umfangreich ist aber nicht so arg haupt zu kapieren dieses struktur
- gramm ist noch nicht ganz fertig gucken wir erstmal wird deklarieren erstmal ne handvoll variablen den gesuchten wert dann deklarieren wie ein wahrheit' werk
- gefunden und noch nicht gefunden wird der clarion index anfang hände und mitte die variablen die wir gerade eben schon die ganze zeit benutzt haben dann lassen
- wir uns den gesuchten werten lesen das heißt wir fragen den user welchen verzugs du wir könnten ihnen auch auf eine beliebige zahl setzen sagen
- gefunden dort mit falls initialisiert gefunden ist ein war heizwert da kann nur wahr und falsch bzw tun falls annehmen
- wir sagen index anfang ist 1 das erste element unseres den wert 1 hat und indexende ist länge des rs noch mal der hinweis falls sie in einer anderen
- programmiersprache operieren und der erste wert des race wäre 0 wäre natürlich indexende länge des arrays - 1 jetzt kommt unsere schleife wir sagen
- 'bitte durchlaufe das folgende vorgehen so oft bis wir unseren wert gefunden haben wir sagen index mitte ist anfang bis
- ende durch zwei haben wir gerade gesehen das machen wir immer am anfang des prozesses verschieden wir die mitte in die mitte sozusagen in die neue mitte
- des restaurants und jetzt prüfen wir ist es unser gesuchter wert dieser mittlere wert falls das der fall ist sagen wir gefunden ist two nachsetzen also die
- wahrheit' variable auf true vorstands ja auch falls falls das nicht der fall ist sagen wir es denn der wert in der mitte größer als unser
- gesuchter wert wenn das der fall ist wissen wir der gesuchte werk muss in der linken beziehungsweise in der ersten hälfte des
- race stecken wir müssen wir also unverändert nach links schieben wir wollen links von damit suchen also ist es neue ende mit minus 1 falls das nicht
- der fall ist heißt es also dass der wert in der mitte kleiner als der gesuchte wert ist gleich kann nicht sein das haben wir hier oben schon überprüft
- falls das der fall ist müssen wir rechts suchen heißt wir müssen den anfang des restaurants nach rechts verschieben also eins rechts von der mitte
- wenn diese schleife durchgelaufen ist überprüfen wir ist gefunden gleich true wenn das der fall ist sagen wir der wert wurde gefunden
- wenn das nicht der fall ist wurde der wert nicht immer gefunden in diesem struktur gramm haben wir noch ein kleines problemchen das programm
- wird nicht korrekt laufen das ist nicht ganz einfach herauszufinden ich gebe ihnen ein tipp was passiert denn wenn sie den wert nicht in ihrer liste haben
- stoppen sie das video gucken sie sich der struktur gramm an und überlegen sie was passiert wenn der überhaupt nicht in der liste ist
- [Musik] [Musik] nehmen wir uns ein beispiel von vielen
- stellen sie sich mal vor wir suchen die zahl acht dann läuft es natürlich so wir sagen 10 ist größer als acht wir müssen also links suchen wir gehen nach links
- sagen fünf die mitte ist kleiner als acht wir müssen also recht suchen gehen wir nach rechts sagen wir neun ist größer als acht wir müssen nach links
- suchen und in diesem fall rutscht indexende nach links und zwar links vom anfang das bedeutet die schleife wird ewig
- laufen index anfang indexende und index mitte bleiben immer an der gleichen position schauen sie in struktur gramm was passiert wenn die schleife jetzt
- weiter läuft wieder und wieder aber das ist auch ein bisschen erfreulich da wir daran erkennen können dass der gesuchte wert offensichtlich
- nicht im ernst wenn also der index ende vor index anfang gerutscht ist wissen wir ja hier gibt es ein problem diesen wert gibt es offensichtlich nicht wir
- haben uns über die meteor und das ende hinaus geschoben deshalb müssen wir in unserer schleife einfach sagen wiederhole die schleife so
- lange bis du den wert gefunden hast oder bis indexende kleiner als index anfang ist wenn das der fall ist sitzt unser
- gefunden werde er immer noch auf falls und bei unserer letzten überprüfung sagt er beinahe hwm den wert nicht gefunden noch ein kurzer hinweis zur rundung oft
- erhalten wir einen ungeraden wert den wir durch zwei teilen müssen wenn wir die mitte bestimmen wollen beispiel index 1 plus index cex gibt siegen durch
- zwei 3,5 ein eray kann aber immer nur ganzzahligen indexwerte haben wir runden also einfach kaufmännisch das heißt aus komma fünf wird für die meisten
- programmiersprachen haben entsprechende rundung funktionen eingebaut und scratch geht das auch zeitig gleich und letztlich kommen wir so immer bei einem
- ganzzahligen wer dann das fertige struktur gramm sieht also so aus wird deklarieren unsere ganzen variablen wir holen uns
- den gesuchten wert wer initialisieren die variablen wie vor ein erklärt jetzt lassen wir die schleife laufen so lange bis wir die zahl gefunden haben oder bis
- ende vor anfang gerutscht ist wir berechnen jeweils die mitte und zwar gerundet da es ja ein indexwert sein soll
- fragen ist das schon unser gesuchter wert wenn ja kann die schleife beim nächsten durchlauf abbrechen da wir gefunden auf true setzen
- falls das nicht auf alles fragen wer ist unser aktueller mittelwert größer als unser gesuchter werden wenn das der fall ist suchen wir links schieben das ende
- falls das nicht der fall ist suchen wir rechts schieben den anfang schauen wir uns an die das ganze in scratch aussehen könnte wir haben hier
- erstmal diese ganzen variablen deklariert dann haben wir uns natürlich auch eine liste gemacht diese liste das kennen sie schon alles gelöscht werte
- hinzugefügt sie haben natürlich längst verstanden dass diese liste sortiert sein muss ansonsten können wir haben nicht sagen befindet sich in der oberen
- oder in der unteren hälfte und so weiter falls eine liste nicht sortiert ist müssen sie die mit bubbles ort oder ähnlichem sortieren aber das können sie
- ja bereits ich habe ja die werte bereits in aufsteigender reihenfolge eingegeben ich lese mir eine zahl ein ich sage user
- gibt mir eine zahl zwischen 1 und 100 prüfen das natürlich nicht sonst ufer des bisschen aus und setzte den gesuchten wert initialisieren mit der
- antwort des users und dann kommt ein blog binäre suche denn hier aufrufe was passiert hier ich initialisieren erstmal diese drei werte dann kommt meine
- schleife und ich sage wiederhole so lange bis gefunden truus oder bis indexende neben den anfang gerutscht ist folgendes
- vorgehen nämlich index mitte auf die mitte setzen also anfang bis ende durch zwei haben wir ausführlich besprochen und dann jeweils überprüfen ist
- dieser index mitte wert schon unser gesuchter wert wenn ja setzte gefunden auf true ansonsten prüfe ob das mittel element links oder rechts vom gesuchten
- wert ist wenn die mitte rechts vom gesuchten element ist dann muss natürlich das restaurant links sein ich muss also links weitersuchen
- ansonsten muss ich rechts weiter suchen wenn die schleife durch gelaufen ist dann frage ich es gefunden true falls ja sage ich da gesuchte wert wurde gefunden
- ansonsten sage ich da gesuchte wert wurde nicht gefunden sie werden es mir nicht glauben das funktioniert ich probiere es aus ich
- suche erst mal nach der 4 die nicht in der liste ist die vier wurde nicht gefunden ist total traurig ich suche nach der 3 d md liste ist aber
- das war schon viel glück beim ausprobieren muss wünsche ihnen einen schönen und erfolgreichen wirken auf
- [Musik]
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.
SuchverfahrenDieser Artikel beschreibt die Suche nach Daten im Kontext der Informatik. Für die Suche nach vermissten Personen und Schiffen siehe Suchmuster. Dieser …
ShakersortDer Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert …