Binäre Suche anschaulich erklärt - mit Übungen [deutsch]
informatikZentrale
https://www.youtube.com/watch?v=jfH_h660gas

Transkript (automatisch erstellt)

0:05 heute beschäftigen wir uns mit der binären suche nachdem er in der letzten folge die relativ einfache aber doch ineffiziente lineare suche
0:14 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
0:25 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
0:34 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
0:50 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
1:18 dafür sieben schritte gebraucht falls sie planen dieses video zur unterhaltung zu schauen dann stecken sie es einfach gehen sie zu netflix machen
1:29 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
1:40 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
1:50 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
2:00 stellen sie ja nein fragen sowie der roboter wenn sie das kapiert haben haben sie drei viertel der mittel bereits
2:10 eingefahren also machen sie es jetzt wahr und ich mit dem roboter auch nochmal spiele
2:18 [Musik] [Musik] ok so einfach kann es gehen jetzt wollen
2:31 wir uns das dings mal bisschen genauer anschauen sie haben bestimmt den trick des roboters herausgefunden erteilt das
2:39 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
2:51 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
3:03 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
3:14 fragt uns also ist deine zahl 75 oder mehr es ist völlig wurscht ob er fragt 75 oder weniger oder 75 oder mehr
3:23 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
3:37 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
3:48 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
4:00 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
4:15 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
4:27 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
4:39 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
4:52 werden wir gleich besprechen es verbleiben nur noch die zahlen 1 70 und 72 er sagt uns ist die zahl 72 oder mehr
5:03 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
5:16 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
5:23 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
5:32 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
5:43 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
5:54 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
6:04 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
6:12 kapieren deshalb bin ich getrost dass ihr leben und ihr verständnis wunderbar sein werden
6:18 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
6:29 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
6:41 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
6:53 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
7:03 relativ einfach dann müssen wir wissen welchen indexwert hat das mittlere element denn wir brauchen ja das mittlere element um den den zahlenraum
7:12 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
7:21 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
7:31 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
7:41 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
7:51 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
8:02 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
8:13 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
8:24 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
8:33 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
8:42 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
8:54 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
9:07 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
9:20 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
9:33 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
9:45 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
9:55 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
10:08 mitte - 1 suchen entsprechend suchen gerecht sind denn wir sagen der index anfang rutscht über definiert einen neuen anfang des restaurants nämlich
10:20 einst hinter damit index plus 1 ehrlich gesagt finde ich und es gut kapieren kann wenn sie damit
10:36 schwierigkeiten haben besteht natürlich auch die möglichkeit ist einfach auswendig zu lernen aber eigentlich wäre kapieren wahrscheinlich smarter dann
10:47 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
10:57 in den meisten anderen programmiersprachen das erste element des rs den indexwert 0 hat aber das wissen sie schon scratch fangen wir mit
11:06 1 an wir erkennen den index anfang das ist nämlich das erste element des also der erste indexwertes 1 der index am ende
11:16 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
11:30 welches ist die erste frage die wir uns stellen wir fragen zuerst ist der mittlere wert identisch
11:45 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
11:55 überprüfen ist der wert links oder ist er rechts dazu sagen wir ist der wert in der mitte
12:14 größer als unser gesuchter wert ist da was richtig 10 ist größer als neun das bedeutet wir müssen in welchem
12:32 bereich des rs suchen im linken bereich das heißt es bleibt uns nur noch ein rest von element 1 bis
12:49 element drei übrig wie kommen wir rechnerisch auf die 3 wir sagen unseren neues ende ist die mitte - 1 da wir
13:07 links von damit suchen danach machen wir das ganze von vorne wie berechnen wir die neue mitte also
13:18 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
13:41 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
13:59 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
14:12 was tun wir haben ist der wert in der mitte größer als
14:25 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
14:49 klar wir suchen rechts von unserem mittelwert unser index anfang wandert also eins rechts neben die mitte der restliche bereich des arrays indem wir
15:05 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
15:15 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
15:27 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
15:40 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
15:51 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
16:05 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
16:18 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
16:29 beziehungsweise den restlichen suchbereich umfang dann wieder von vorne an wir definieren die mitte wir schauen ob
16:37 in der mitte unser gesuchter wert steht falls nicht schauen wir ob unser gesuchter wert links oder rechts der mitte steht entsprechend definierung der
16:47 neuen anfang bzw neues ende als das restaurant dann fangen wir wieder an mir sagen was ist denn die mittel wir schauen ist in
16:56 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
17:05 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
17:19 gramm umgesetzt ich zeige ihnen struktur gramm das erstmals erwischt aussieht sehr sehr umfangreich ist aber nicht so arg haupt zu kapieren dieses struktur
17:30 gramm ist noch nicht ganz fertig gucken wir erstmal wird deklarieren erstmal ne handvoll variablen den gesuchten wert dann deklarieren wie ein wahrheit' werk
17:39 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
17:48 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
17:58 gefunden dort mit falls initialisiert gefunden ist ein war heizwert da kann nur wahr und falsch bzw tun falls annehmen
18:06 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
18:18 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
18:30 'bitte durchlaufe das folgende vorgehen so oft bis wir unseren wert gefunden haben wir sagen index mitte ist anfang bis
18:41 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
18:50 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
19:03 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
19:15 gesuchter wert wenn das der fall ist wissen wir der gesuchte werk muss in der linken beziehungsweise in der ersten hälfte des
19:23 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
19:35 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
19:45 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
19:56 wenn diese schleife durchgelaufen ist überprüfen wir ist gefunden gleich true wenn das der fall ist sagen wir der wert wurde gefunden
20:06 wenn das nicht der fall ist wurde der wert nicht immer gefunden in diesem struktur gramm haben wir noch ein kleines problemchen das programm
20:15 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
20:26 stoppen sie das video gucken sie sich der struktur gramm an und überlegen sie was passiert wenn der überhaupt nicht in der liste ist
20:35 [Musik] [Musik] nehmen wir uns ein beispiel von vielen
20:50 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
21:04 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
21:15 suchen und in diesem fall rutscht indexende nach links und zwar links vom anfang das bedeutet die schleife wird ewig
21:24 laufen index anfang indexende und index mitte bleiben immer an der gleichen position schauen sie in struktur gramm was passiert wenn die schleife jetzt
21:34 weiter läuft wieder und wieder aber das ist auch ein bisschen erfreulich da wir daran erkennen können dass der gesuchte wert offensichtlich
21:44 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
21:57 haben uns über die meteor und das ende hinaus geschoben deshalb müssen wir in unserer schleife einfach sagen wiederhole die schleife so
22:04 lange bis du den wert gefunden hast oder bis indexende kleiner als index anfang ist wenn das der fall ist sitzt unser
22:14 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
22:25 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
22:35 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
22:48 programmiersprachen haben entsprechende rundung funktionen eingebaut und scratch geht das auch zeitig gleich und letztlich kommen wir so immer bei einem
22:56 ganzzahligen wer dann das fertige struktur gramm sieht also so aus wird deklarieren unsere ganzen variablen wir holen uns
23:04 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
23:15 ende vor anfang gerutscht ist wir berechnen jeweils die mitte und zwar gerundet da es ja ein indexwert sein soll
23:23 fragen ist das schon unser gesuchter wert wenn ja kann die schleife beim nächsten durchlauf abbrechen da wir gefunden auf true setzen
23:31 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
23:40 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
23:49 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
24:00 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
24:09 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
24:17 ja bereits ich habe ja die werte bereits in aufsteigender reihenfolge eingegeben ich lese mir eine zahl ein ich sage user
24:27 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
24:38 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
24:50 schleife und ich sage wiederhole so lange bis gefunden truus oder bis indexende neben den anfang gerutscht ist folgendes
25:00 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
25:10 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
25:24 wert ist wenn die mitte rechts vom gesuchten element ist dann muss natürlich das restaurant links sein ich muss also links weitersuchen
25:34 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
25:44 ansonsten sage ich da gesuchte wert wurde nicht gefunden sie werden es mir nicht glauben das funktioniert ich probiere es aus ich
25:51 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
26:03 das war schon viel glück beim ausprobieren muss wünsche ihnen einen schönen und erfolgreichen wirken auf
26:11 [Musik]