Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Lineare Suche & Binäre Suche einfach erklärt - Suchalgorithmen lernen [001]
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 161 Zeilen
- hallo und herzlich willkommen zu diesem ersten video in der videoreihe algorithmen und zwar beschäftige ich mich in jedem video dieser reihe mit
- einem oder mehreren algorithmen die zu einem bestimmten thema passen und heute schauen wir uns die lineare und die binäre suche an also wir kümmern uns um
- such algorithmen aber zunächst und das ist ganz passend für das erste video schauen wir uns erst mal an was ist ein algorithmus überhaupt algorithmus das
- wort dafür und das ist ein definierter ablauf zur lösung eines problems das heißt wir definieren so arbeitsschritte wie so ein kochrezept und kommen dann
- von einem zustand in dem wir nicht haben wollen in einen zustand den wir haben wollen also wir haben ein problem gelöst und genau das kann man sich so ein
- bisschen vorstellen wie wir haben eine definierte eingabe für einen algorithmus der algorithmus tut an irgendwas verarbeitet diese daten und gibt dann
- irgendetwas aus das heißt was im idealfall halt das problem für uns löst so kann zb das sortieren wunderbar durch algorithmen
- gelöst werden das heißt wir haben eine unsortierte liste oder was auch immer der algorithmus sortiert das dann um die ausgabe ist daneben die sortierte liste
- sortier algorithmen sind übrigens sehr wichtig und deswegen schauen wir uns die auch an aber heute soll es uns suchen gehen
- wir suchen als problem versuchen wir das ganze mal so in dieses reglement rhein zu pressen was wir jetzt gerade kennengelernt haben wir haben eingabe
- beim suchen ist halt eine liste von elementen zum beispiel von zahlen es können aber auch texte das könnten bücher sein das kann alles mögliche sein
- diese liste muss nicht sortiert sein die kann wild durcheinandergewürfelt sein hauptsache sie hat eine reihenfolge also ist es eine liste und unser problem ist
- jetzt wir wollen wissen ob ein element was wir haben in dieser liste enthalten ist und wenn ja an welcher stelle das heißt zum beispiel hier unten haben wir
- mal als beispiel eine liste von von ganzen zahlen die nicht sortiert ist und wir wollen jetzt wissen ist die zwei in dieser liste enthalten und wenn ja an
- welcher stelle sehen wir als menschen natürlich sofort klar die ist da drin an vierter stelle sieht man doch an der computer muss dafür aber erst mal
- tatsächlich ein verfahren anwenden um zu schauen ist diese zahl denn überhaupt in der liste drin genau zwei dieser verfahren werden wir uns jetzt anschauen
- und wir fangen an mit dem verfahren der linearen suche ich habe also diese liste jetzt mal ein bisschen anders hin geschrieben und oben rechts die zahl in
- dem gestrichelten gelben kreis die zählt uns jetzt mal die schritte in dieser verarbeitung in dieser suche mit ungleich ganz einfach mit dem zweiten
- algorithmus vergleichen zu können wie viele schritte werden gebraucht haben und um das abzuschätzen zu können welcher algorithmus denn möglicherweise
- schneller ist so also wir suchen das element 2 und die lineare suche ist jetzt wirklich straight forward wir fangen von links an und gucken ist das
- erste element unserer gesuchtes element das heißt wir schauen schritt nummer eins oben rechts und die eins ist die 2 am ersten an erster
- stelle steht fünf deswegen wird der vergleichsfall hier roth wir müssen weiter suchen so dann schauen wir weiter ist an der zweiten
- stelle unsere zwei natürlich auch nicht dann schauen wir weiter ist an der dritten stelle die 2 ganz einfach schema f w wiederholen dass immer wieder ist es
- auch nicht und jetzt kommen wir endlich an der stelle an der vierten jahren da ist unsere zwei wir sind am ende und können jetzt sagen an position vier
- befindet sich dieses element wunderbar relativ einfach linear heißt die suche deswegen weil wir halten linear von links nach rechts
- wie in einer linie die liste durchsuchen durchblättern quasi das wäre zum beispiel analog wenn man jetzt einen weg von karten hätte von spielkarten und man
- würde eine bestimmte karte suchen und müsste man auch von vorne jede einzelne karte durchgehen weil man sich nicht alle karten
- gleichzeitig angucken kann es sei denn man möchte sie alle auf den tisch legen das dauert aber meistens länger als einfach die karten eins zu eins durch zu
- geben so jetzt schalten wir mal kurz in netbeans und gucken uns mal ein stückchen java code an was diese lineare suche implementiert das habe ich nämlich
- für euch mal gemacht ich schalte mal kurzum wir sehen jetzt hier ich habe hier mal in einer kleinen methode die lineare suche implementiert wir sehen
- hier ganz schön die lineare suche über bekommt übergeben einen integer wert also eine zahl die wir suchen innerhalb der liste dann bekommt sie einen ein
- integrer übergeben was die liste enthält kurz noch mal als querverweis zu meiner anderen videoreihe grundlagen der programmierung wenn euch das jetzt alles
- hier nichts sagt das ist nicht schlimm [Musik] ihr könnt das abklären schaut er gerne in der videoreihe grundlagen der
- programmierung nach dann werdet ihr über methoden über integre race über schleifen aufgeklärt und das ist sehr spannend und macht natürlich auch sinn
- wenn man sich über algorithmen informiert auch ein bisschen in die programmierung zu schauen und umgekehrt und gerade der umgekehrte weg zurück zum
- algorithmus also wir übergeben die liste und das gesuchte element und zurück gibt die funktion uns ein internet das ist jetzt allerdings nicht das gesuchte
- element das wäre ja einfach nein das ist die position innerhalb der liste an der sich das gesuchte element befindet oder die zahlen - einst als stellvertretendem
- wert dafür falls das element nicht gefunden wurde und jetzt schauen wir uns mal das innenleben dieser methode ein wenig
- genauer an hier ist der algorithmus im prinzip wie wir ihn gerade gesehen haben implementiert und zwar gibt es eine
- schleife diese schleife läuft von 0 bis zur länge der liste liest punkt längst ist die länge der liste und zwar läuft sie so lange wie kleiner ist als die
- länge der liste und mit jedem durchlauf dieser schleife erhöhen wir die variable die hero vorne ja auf null gesetzt wird um 1 und jetzt geben wir die liste durch
- also wir sind jetzt beim ersten element listen race fangen immer werden fangen wir beim 0 1 element in der programmierung an und gucken jetzt ob
- unser gesuch des elements das element in der liste ist und wenn ja dann geben wir das geben wir die position nämlich die unsere zähler variable ii einfach zurück
- wenn nicht geht die schleife ein zweiter wird um 1 erhöht wir sind jetzt bei der position eins und dann schauen wir wieder ist das gesuchte element jetzt
- gerade an unserer position wenn ja geben wir es zurück wenn nicht geht es weiter und so weiter bis wir am ende der liste angekommen sind das heißt wenn der
- listen länge entspricht dann sind wir am letzten element angekommen und dann wenn wir es dann immer noch nicht gefunden haben dann gehen wir einfach die - 1
- zurück relativ einfach und bringt uns zum ergebnis sehen wir hier aber auch wenn man das mal so revue passieren lassen
- wenn wir gerade gesehen an der vierten stelle brauchen wir genau vier operationen um das element zu finden und im worst case brauchen wir dann also so
- viele operationen wie die liste lang ist das heißt bei ganz ganz langen listen ist diese lineare suche natürlich zeitaufwendig wir schauen uns jetzt
- nochmal das ganze an wenn es laufen lassen dafür habe ich hier oben das kommentiere ich nochmal aus das sehen wir nämlich gleich dafür habe ich das
- hier oben nämlich mal laufen lassen also ich hole mir eine liste von entwerten ein engel von entwerten und zwar geht das von ist es eine zufällige liste und
- die geht von null bis die enthält werte die zwischen 0 und 1 und 10.000 sind und sie ist 10.000 elemente lang und unser such wert der ist auch eine zufällige
- zahl zwischen null und 10.000 dann gebe ich aus welchen wert wir suchen dann wenn dich die lineare suche an und gebe aus an welcher position ich sie gefunden
- habe und noch mal zur sicherheit welches element sich dann an der position in der liste findet und das muss ja dann genau das gesuchte sein
- das kann zu lassen wir jetzt mal laufen so wir suchen wie 1751 und haben gesehen in unserer 10.000 zeichen oder 10.000
- zahlen langen liste ist dieses an position 6201 und der wert ist 1751 das hier ist natürlich gleich deswegen hat das natürlich geklappt wir jetzt aber
- gemerkt haben bei langen listen und mit langen listen meine ich keine 10.000 elemente wie gesehen habt geht das ratzfatz nein lange listen sind wirklich
- millionen milliarden billionen elemente in datenbanken würde man selten ist oder nur im notfall wenn nichts anderes geht nicht lineare suche machen und da wird
- dann auch relativ schnell relativ langsam wir schauen wir uns jetzt aber nochmal eine effizientere art der suche und zwar
- die sogenannte binäre suche die binäre suche hat einen kleinen unterschied und das ist hier gelb markiert und zwar ist die eingabe eine sortierte liste von
- elementen das heißt die darf nicht wild durch gewürfelt seien die muss sortiert sein ist schon mal nachteil gegenüber der linearen suche und das problem ist
- dasselbe wieder bei der linearen suche wir wollen wissen wenn ja also wenn das element enthalten ist wo ist es denn und ich habe hier jetzt auch schon mal
- eine sortierte liste von 1 bis 10 das sind einfach die zahlen von eins bis zehn sie könnten auch doppelt vorkommen habe ich jetzt aber nicht gemacht der
- einfachheit halber und wir suchen jetzt die 3 so auch hier wieder oben rechts die anzahl der schritte in einer liste mit
- zehn elementen das ist jetzt also doppelt so lang wie vorhin und dann fangen wir an und zwar läuft die binäre versuche jetzt so ab wie ihr seht schon
- wir suchen uns einem element was sehr nahe in der mitte ist bei einer liste von zehn zahlen ist das natürlich entweder die fünfte die sechste position
- ich habe mich jetzt mal dafür entschieden die linke von den beiden zahlen zu nehmen also die mitte wäre ja 5,5 und dann habe ich einfach die
- nachkommastellen abgeschnitten wir schauen uns also das mittlere elemente an dass mittels der element der minister und gucken ist dass unser gesuchtes
- elemente in dem fall nicht und jetzt gucken wir nochmal ist denn dieses element was wir gerade betrachtet haben größer oder kleiner als das element was
- wir gerade haben in dem fall würde ich sagen unser gesuch des element ist definitiv kleiner als die 53 ist kleiner als fünf und dann
- wissen wir ja weil die liste sortiert ist alles was jetzt größer ist als das element was wir uns gerade angeguckt haben das kann es ja schon mal nicht
- sein weil jetzt kommen wir nur noch zahlen die größer als 5 sind das heißt wir blenden quasi die liste aus die rechts von unserem angeschauten elemente
- ist genau und jetzt machen wir das fange wieder von vorne an wir nehmen wieder die mitte der verbleibenden liste jetzt kleiner ist halb so klein um genau zu
- sein und gucken uns wieder an ist das unser gesuch des element nähe ist diesmal auch nicht die 2 jetzt wissen wir aber die zwei ist kleiner als unser
- gesucht das element die drei das heißt jetzt ist links von dem von unserem betrachteten element alles nicht dichter kann unsere zahlen nicht mehr vorkommen
- das heißt wir schließen dass auch auf zack und jetzt von den zwei elementen die mitte ist jetzt 3,5 dann habe ich mich auch entschieden dass linke zu
- nehmen das ist jetzt zufällig das richtige hätte ich mich jetzt am anfang des algorithmus dafür entschieden das rechte zu nehmen wären wir jetzt
- noch einen schritt vom ergebnis entfernt aber wir sehen jetzt jetzt ist es das richtige element wir haben quasi unser ziel erreicht und das nach nur drei
- schritten quasi nun wir sehen schon bei einer liste die zehn elemente lang ist nur drei schritte zu brauchen das schafft die lineare suche nur wenn das
- element auch an der dritten stelle ist würden wir jetzt die zehn suchen in dieser liste bräuchte sie zehn vergleichen
- die lineare suche wohingegen die binäre suche immer noch kürzer wäre und das ist in der tat für alle fälle so jetzt haben wir uns noch mal ganz kurz
- auch hier die implementierung in java an wir gehen wieder zurück in netbeans und jetzt kann ich das hier auch aus kommentieren ich habe dasselbe was ich
- hier oben angewendet habe auch für die binäre suche gemacht hier finden wir sie wir gucken uns aber zunächst einmal die funktion binäre suche an beine research
- da brauch ich glaube ich ein bisschen mehr platz hier so wie es jetzt ein bisschen länger ein bisschen kompliziert habe weil der algorithmus noch ein
- bisschen komplizierter ist wir kriegen wieder das such element und die liste übergeben und wir geben wieder die position des
- gesuchten elements innerhalb der liste zurück oder die - einst so zunächst definieren wir zwei variablen und zwar die start und and start und sind quasi
- der teil der liste also das erste und das letzte element innerhalb dieser liste was den teil definiert indem wir noch suchen wollen das war der teil den
- ich vorhin in der präsentation in der in der animation nicht ausgeblendet hatte also der ja der bunte teil denken wir der schwarze teil das war der der jetzt
- quasi außen vor war und dann schauen wir so lange start und endpunkt ja nicht derselbe sind das heißt also solange wir noch platz zum
- suchen haben suchen wir auch und wir berechnen jetzt wie wir gerade im algorithmus auch gesehen haben dass mit letzte element das ist mathematisch
- jetzt ein bisschen komplizierter ausgedrückt wir schauen erst mal wie lang ist die liste überhaupt die wir hier so betrachten teilen das ganze
- durch zwei das ist das mittlere element in java muss man wissen wenn man integer werte durch zwei teil dann ist das die integra division die ganze zahl der
- vision das heißt er schmeißt die nachkommastellen auch weg passt uns ganz gut wir haben ja gerade auch immer das linkeste element betrachtet wenn die
- hälfte halt zwischen zwei elementen war und wir müssen natürlich noch den startwert obendrauf rechnen weil es könnte ja sein dass wir nicht am anfang
- unserer ursprünglichen liste anfangen sondern wir bereits schon von links auch als abgeschnitten haben das ganze berechnet uns also das element was wir
- uns gerade betrachten und das prüfen wir dann auch die rag ist noch gerade betrachtete mittlere element denn unser gesuch des element wenn ja dann geben
- wir direkt diese element position quasi zurück dass es dann unser ergebnissen wenn nicht müssen wir noch schauen ist denn das element was wir gerade
- betrachtet haben dieses mittel element ist das jetzt größer oder kleiner unseres gesuchten elementes wenn es größer ist heißt das ja dass links von
- uns in der liste das gesuchte element sein muss rechts kann es nicht mehr sein das heißt wir setzen das ende auf das gesuch jetzt
- gerade angeguckt element das heißt wir schneiden von rechts alle elemente weg und gucken jetzt nur noch bis zu dem element was wir gerade
- angeguckt haben ist das gerade angeguckt center element den kleiner als search dann setzen wir den staat wert auf den center wert also auf das element was wir
- gerade bei uns angeguckt haben weil wir von links abschneiden hier ist noch zu beachten wir setzen den
- wir schneiden von links ein element mehr ab das hat den grund wenn wir das nicht tun würden würden wir irgendwann am 1 an einer stelle ankommen an den start
- und enden noch 1 voneinander entfernt sind [Musik] wir arbeiten uns da nicht weiter bewegen
- also es bleibt dann immer bei einer bei der entfernung 1 und die werden nie aufeinander geschoben das heißt der algorithmus würde in dem fall dann nie
- zum ende kommen wäre schlecht und das machen wir so lange wir berechnen also von dieser neuen start und endwert situation wieder die mitte schauen uns
- die mitte an ist es das nicht verkürzen wir wieder links oder rechts die liste und machen weiter bringt das irgendwann das ganze nicht zum ziel das heißt den
- start und endwert jetzt gleich das heißt hat betreffen wir zu noch ein einziges element und dann ist die schleife vorbei dann sagen wir okay das element ist es
- ja wohl auch nicht das element ist in dieser liste nicht enthalten und wir geben die - 1 zurück und das kann man jetzt auch gerade mal
- ausführen natürlich darauf möchte ich euch noch mal speziell hinweisen hier oben ist das linear die lineare suche wir schauen jetzt hier noch mal ob
- wir was ausgeben müsste überhaupt nichts gefunden wurde das kann ja auch sein und danach sortiere ich die liste das ist die voraussetzung für die binäre suche
- dass die liste sortiert ist jetzt vorher haben wir uns ja nie zufällige liste generiert die waren nicht sortiert logischerweise und dann mache ich genau
- dasselbe wie hier oben mit der lineare besucher auch ich wende sie an und gucke bedienen die position an und gebe dementsprechend je nachdem ob was
- gefunden wurde oder nicht die zwei textzeilen aus um das machen wir jetzt auch gerade mal und wir haben jetzt einen fall gehabt okay wir suchen die
- sieben 1941 und natürlich die beiden suchen in derselben liste nur einmal sortiert einmal nicht die dürften natürlich wenn sie nichts finden nichts
- finden beide wohlbemerkt das schauen wir uns also noch mal an und nochmal bis wir mal ein ergebnis haben wo was gefunden wurde
- hier zum beispiel wir suchen die 9000 7 50 und in der unsortierten liste hat die lineare suche das element an der stelle 9 1681 also relativ weit hinten logisch
- ist ja auch eine sehr relativ weit hinten ist nicht logisch ist ja umsortiert gefunden und zum check nochmal den wert an dieser stelle
- ausgegeben und das ist tatsächlich unser gesuch das element bei der binären suche ist es jetzt eine andere position logisch weil es wurde ja sortiert jetzt
- ist sich logisch dass die 9750 relativ weit hinten in dieser liste ist nämlich beim 9 1755 wert weil die ist ja sortiert das heißt die hohen zahlen sind
- am ende und auch hier ist unser gefundenes element 9750 das heißt das stimmt und
- genau der unterschied ist allerdings dass wir hier unten das sehen wir jetzt natürlich nicht aber nur relativ wenige ich würde schätzen 13 oder 14 schleifen
- durchläufe gebraucht haben während wir hier oben ja auf jeden fall 1681 schleifen durchläufe gebraucht haben weil wir von links dass ihr
- zurückgeben das ist ja genau diese zahl hier das heißt diese zahlen muss bis 9 1681 gelaufen sein das heißt das ist ja schon
- eine sehr große anzahl an schleifen würde ich jetzt mal sagen während wir hier unten wahrscheinlich nur 13 bis 14 schleifen durch läufe
- gemacht haben weil wir immer wieder die hälfte von 1000 weggeschmissen haben also dann nach dem ersten durchlauf waren sie nur noch 500 elemente 250
- elemente 125 elemente und so weiter und so fort das heißt hier kommen wir relativ schnell zum ergebnis ist muss aber nur
- sortierte liste sein und ja das thema das nennt sich komplexität das schauen wir uns auch noch mal ganz kurz an die lineare suche
- die läuft im schlechtesten fall wir gucken uns immer den schlechtesten fall an so lang wie die liste ist also das element steht ganz links oder es kommt
- gar nicht vor da muss die lineare suche einmal durch die gesamte liste rauschen gucken ist das überhaupt richtig da drin
- das nennt sich die komplexität die wird immer in der schreibweise und dann in klammern und dann eine formel angegeben das ist die große uhr schreibweise und
- hier ist es so von nn ist eine variable aus der mathematik kennt man und n ist halt die anzahl der elemente in der liste macht sind also der schlechteste
- fall ist immer um die laufzeit ist so lang wie die liste die komplexität bei der bienen ehren suche ist es anders da ist es immer weniger als die listen
- länge und smart teilen wir die listen länger immer wieder durch zwei bissen wir sind nicht mehr geht es nicht mehr teilbar ist und wer jetzt ein bisschen
- mathematik kann der wird direkt daran denken das ist doch logarithmisch von 2 das ist also logarithmisch und das gucken wir uns gleich mal in dem
- diagramm an wie denn eine logarithmische verlauf ist und dann wenn wir dann genau sehen dass das auf jeden fall schneller ist und das machen jetzt auch gerade mal
- die haben wir also ein kleines diagramm habe ich mitgebracht einmal eine lineare funktion und einmal die logarithmische funktion die es ein bisschen angepasst
- kann wundert euch nicht wer es genau wissen will das ist der logarithmisch zur basis 2 von enplus 1 muss aber nicht interessieren wichtig
- ist die komplexität der binären suche ist lockt von enden und wir sehen hier das können wir mal gemeinsam gucken wir schauen mal auf der x-achse ist die
- listen länge aufgetragen und auf der y-achse die berechnung schritte bei der linearen suchen wir gucken mal bei fünf elementen brauchen wir fünf berechnungs
- schritte das macht sinn maximal im schlechtesten fall wir gucken jetzt für unser beispiel bei 10 elementen für die binäre suche
- bräuchten wir nur 4,1 ein paar zerquetschte durchläufe also vier durchläufe kann ja kein halben schleifen durchlauf machen das geht nicht
- das ist natürlich deutlich schneller als die lineare suche die im schlimmsten fall zehn durchläufe bräuchte jetzt ist komplexität aber nicht gleich
- komplexität denn wir sehen jetzt natürlich noch mal lineare suche ist offen also linear wie wir gerade gesehen haben
- binäre suche hat eine komplexität von roll okay das ist jetzt ein bisschen besser je mehr elemente desto also bei hohen element zahlen bleibt es immer
- noch schön niedrig in der komplexität in der laufzeit in den schleifen durchläufen aber wir hatten ja diese voraussetzung dass die binäre suche eine
- linie quatsch eine sortierte liste als eingabe brauche jetzt haben wir nicht immer neu sortierte liste das heißt wenn wir wirklich die beiden
- algorithmen gegeneinander antreten lassen wollen würden so eins zu eins mit gleichen voraussetzungen dann müssten wir ja binären suche immer noch nur
- liste muss sortiert sein auch die komplexität des sortier algorithmus mit drauf rechnen haben wir gerade im code auch gesehen ich muss die liste vorher
- mit race punkt sword sortieren das heißt das kostet natürlich auch noch mal zeit jetzt gibt es aber ganz ganz viele fälle
- wo wir schon eine sortierte liste haben oder wo wir die liste sowieso sortieren weil wir das brauchen in den fällen können wir dann im
- anschluss natürlich viel besser die binäre suche machen weil die dann nicht noch mal eine lineare laufzeit oben drauflegt das heißt man muss immer im
- anwendungsfall abwägen welchen algorithmus man denn jetzt braucht und da auch mal noch mal genau hingucken ob die algorithmen die man da vergleicht
- auch wirklich vergleichbar sind ich würde sagen eure aufgabe ist jetzt dass ihr mal versucht in java oder in
- der programmiersprache eurer wahl die lineare und die binäre suche zu implementieren schaut mal erschöpft wenn ihr noch nicht
- so weit seien im programmieren kein problem schaut euch meine videos zu den grundlagen zum programmieren an
- ich würde sagen spätestens ab zwei dritteln ab der hälfte dieses kurses müsstet ihr soweit sein und diese algorithmen implementieren können und
- das macht ganz ganz viel spaß schaut mal ob wir vielleicht auch einbauen können dass sie die schleifen durchläufe zählt um die werde dann sehen dass die binäre
- suche mit den richtigen voraussetzungen natürlich viel viel effizienter ist wenn man sowieso sortieren muss wenn man nicht sortieren muss dann würde ich dann
- doch lieber die lineare suche nehmen schaut mal wie ihr das spielt einfach mal ein bisschen damit rum ich würde sagen wir sehen uns im
- nächsten video bis dann
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 …
ZeitkomplexitätUnter der Zeitkomplexität wird in der Informatik die Anzahl der ... Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet …