Binäre Suche in 5 Minuten | Algorithmen und Datenstrukturen
Turing Informatik
https://www.youtube.com/watch?v=RiWgK7BhTQI

Transkript (automatisch erstellt)

0:00 die binäre suche ist ein such algorithmus der in sortierte race elemente in logarithmische zeit komplexität findet hier haben wir eine
0:07 liste von menschen mit zugegeben sehr kurzen telefonnummern diese liste ist nach den telefonnummern aufsteigend sortiert und das ist eine sehr wichtige
0:14 voraussetzung gerade kam ein anruf mit der telefon nummer 32 und wir wollen jetzt wissen wer zu dieser nummer gehört der ansatz der binären suche ist es nun
0:23 zunächst das element in der mitte anzuschauen und mit der nummer zu vergleichen 25 ist ihr kleiner als die gesuchte 32 und da das resultiert ist
0:32 wissen wir dadurch dass das gesuchte element rechts von der 25 liegen muss wir müssen also nur noch dort weiter suchen und können den rest ignorieren
0:40 somit wurde der suchbereich in einem einzigen schritt bereits um die hälfte verkleinert und wir werden nun dieselbe strategie einfach auf den neuen
0:47 suchbereich an vergleichen also das mittlere element unseres neuen such bereichs mit der 32 und wieder muss das ergebnis rechts von diesem element
0:56 stehen und wir können einen großen teil des aktuellen suchbereich eliminieren und der letzte vergleich führt hier in dem fall zum erfolg und wir wissen dass
1:03 real angerufen hat wir haben also in gerade einmal drei schritten ein array der länge 11 erfolgreich durchsucht und da wir mit jedem schritt die hälfte des
1:11 bereichs ausschließen können also das problem auf die hälfte reduzieren ist die zeit komplexität dieses logarithmisch von locken und da wir eben
1:19 jedes mal die problem größe halbieren und dann dieselbe strategie auf das neue problem an wänden handelt es sich hier um einen die weit in kongo algorithmus
1:28 und da wir außerdem nur auf dem eingabe ray arbeiten und keinen weiteren speicher benötigen ist die platz komplexität in ofen 1 hier nochmal eine
1:36 abstrakte beschreibung des algorithmus wir starten also mit einem sortierten array mit den elementen x0 bissig sandy aufsteigend sortiert sind
1:44 und um es zu finden wählen wir zuerst das mittlere element aus a und falls sie also das mittlere element gleich unseren gesuchten element ist
1:53 wären wir bereits erfolgreich und fertig falls es aber größer ist als exil müssen wir rechts weiter suchen und ansonsten links und dazu aktualisieren wir jeweils
2:03 auf den neuen suchbereich und wiederholen dem prozess einfach es gibt jetzt zwei möglichkeiten die binäre suche zu implementieren nämlich relativ
2:10 und interaktiv und wir schauen uns zunächst die regressive kommentierung an und diese konkrete implementierung sucht in einem interview
2:18 der länge m nach dem element ickx und wenn dieses existiert wird dessen index im array zurückgegeben und falls das nicht existiert dann eine -1 die
2:27 funktion bekommt als parameter das zu durchsuchen das zu suchen der element ickx und außerdem die indizes der elemente die den aktuellen suchbereich
2:35 einschränken hier zum beispiel fangen wir mit l gleich null und er gleich zehn an also mit dem gesamten bereich und an einem
2:42 späteren schritt indem wir dann schon den suchbereich verkleinert haben ist lzb 6 und dann schränken wir das immer weiter ein
2:49 und tatsächlich sehen wir hier unten dass die funktion am anfang mit l gleich null und er gleich der größte minus 1 aufgerufen wird das heißt wir
2:58 durchsuchen im ersten schritt natürlich das gesamte ray als erstes checken wir jetzt ob er größer gleich l ist das ist genau dann nicht mehr der fall wenn das
3:06 gesuchte element iks nicht immer enthalten ist und in diesem fall würden wir dann einfach eine - einst als ergebnis zurück geben ansonsten
3:13 berechnen wir zunächst den index des mittleren elements des aktuellen suchbereich hier als variable und es ist wichtig zu beachten dass wir hier
3:21 abrunden müssen was in diesem fall durch die verwendung von und automatisch passiert aber zum beispiel in javascript muss man hier maß punkt floor anwenden
3:28 da javascript ja nicht streng typisiert und das dann einfach ein double wird im nächsten schritt schauen wir jetzt ob das mittlere element schon unsere
3:35 gesuchte sixx ist falls ja geben einfach dessen index zurück und sind fertig falls hingegen das gesuchte element kleiner ist als das mittlere element
3:43 wissen wir dass sich das gesuchte element links vom mittleren element befindet wir rufen jetzt also einfach die funktion re kursiv auf verschieben
3:50 aber die rechte grenze auf das element links vom aktuell mittleren element also auf den index im minus 1 wir suchen also die kursiv im verkleinerten suchbereich
4:00 weiter und irgendeine der rezessions aufrufe wird das element an finden oder eben feststellen dass es nicht mehr existiert und ein index zurück geben den
4:08 wir dann durch das return stufe um stufe nach oben weiter geben bis wir es dann aus dem obersten call der funktionen an den aufrufenden court zurückgeben und
4:16 genauso verfahren wir in dem fall das ixs größer ist als das mittlere element hier setzen wir die linke beschränkung des neuen suchbereich entsprechend auf
4:23 das element rechts vom aktuellen ein element also auf m + 1 die iterative implementierung sieht im wesentlichen sehr gleich aus und funktioniert von der
4:34 logik auch exakt gleich zusammenfassend durchsucht die binäre suche also ein bereits sortiertes array mit zeit komplexität von locken wobei der best
4:44 case nämlich wenn das gesuchte element direkt in der mitte des arrays liegt eine zeit komplexität von ufern 1 hat es handelt sich um einen klassischen gewalt
4:52 im kongo algorithmus und da wir keinen weiteren speicher belegen ist die platz komplexität von konstanter ordnung das war es auch schon wieder vielen dank
5:00 fürs zuschauen über einen like und aber würde ich mich natürlich sehr freuen außerdem könnt ihr mich über paypal unterstützen den link dazu findet ihr in
5:07 der video beschreibung bis zum nächsten mal [Musik]