Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Binäre Suche in 5 Minuten | Algorithmen und Datenstrukturen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 39 Zeilen
- die binäre suche ist ein such algorithmus der in sortierte race elemente in logarithmische zeit komplexität findet hier haben wir eine
- liste von menschen mit zugegeben sehr kurzen telefonnummern diese liste ist nach den telefonnummern aufsteigend sortiert und das ist eine sehr wichtige
- 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
- 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
- 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
- somit wurde der suchbereich in einem einzigen schritt bereits um die hälfte verkleinert und wir werden nun dieselbe strategie einfach auf den neuen
- suchbereich an vergleichen also das mittlere element unseres neuen such bereichs mit der 32 und wieder muss das ergebnis rechts von diesem element
- 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
- 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
- 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
- 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
- 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
- abstrakte beschreibung des algorithmus wir starten also mit einem sortierten array mit den elementen x0 bissig sandy aufsteigend sortiert sind
- 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
- 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
- auf den neuen suchbereich und wiederholen dem prozess einfach es gibt jetzt zwei möglichkeiten die binäre suche zu implementieren nämlich relativ
- und interaktiv und wir schauen uns zunächst die regressive kommentierung an und diese konkrete implementierung sucht in einem interview
- 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
- funktion bekommt als parameter das zu durchsuchen das zu suchen der element ickx und außerdem die indizes der elemente die den aktuellen suchbereich
- einschränken hier zum beispiel fangen wir mit l gleich null und er gleich zehn an also mit dem gesamten bereich und an einem
- späteren schritt indem wir dann schon den suchbereich verkleinert haben ist lzb 6 und dann schränken wir das immer weiter ein
- 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
- 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
- gesuchte element iks nicht immer enthalten ist und in diesem fall würden wir dann einfach eine - einst als ergebnis zurück geben ansonsten
- berechnen wir zunächst den index des mittleren elements des aktuellen suchbereich hier als variable und es ist wichtig zu beachten dass wir hier
- 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
- 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
- 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
- wissen wir dass sich das gesuchte element links vom mittleren element befindet wir rufen jetzt also einfach die funktion re kursiv auf verschieben
- 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
- 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
- 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
- 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
- das element rechts vom aktuellen ein element also auf m + 1 die iterative implementierung sieht im wesentlichen sehr gleich aus und funktioniert von der
- logik auch exakt gleich zusammenfassend durchsucht die binäre suche also ein bereits sortiertes array mit zeit komplexität von locken wobei der best
- 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
- 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
- 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
- der video beschreibung bis zum nächsten mal [Musik]