[Playlisten] [Impressum und Datenschutzerklärung]

S12B binäre Suche programmieren; Laufzeitkomplexität


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

noch weiter zu sortieren – und suchen – wenn ich eine sortierte Liste habe ?? – ABC – oder CP wie auch immer – die F – G H I – HWG zweiter G H I J – J wir Komma wenn ich die sortierte Liste habe kann ich darin relativ schnell suchen – durch fortlaufendes – halbieren – das war ich auch mit ihm durch exerzieren – dass es eine – wesentliche Anwendung für Satiren – wenn ich schnell suchen will – sortiere ich erst – vorher ein einziges Mal dann kann ich danach Millionen mal schnell suchen – das ist übrigens auch ?? Funktion eingebaut ?? C genauso wie das – Sortieren in C eingebautes versuchen eingebaut Leerzeichen alle neueren Sprachen – es kann aber ?? helfen sich das zu Fuß anzugucken und nebenbei kommen ?? mal was Überweisungstricks – lernen zu Wiederholung – was ich suchen will sind – dann – Telefonbucheinträge – damit von Komma an und schreiben Sie mal gerade zur Übung – eines Trakt – in der stehen soll eine Zeichenkette – für den Nachnamen – eine Zeichenkette – für den Vornamen – und eine Telefonnummer – lassen die Datensätze in den nicht gleich – suchen will – dafür eines Trucks zu schreiben – erst mal – das Essen schöner Name nennen Sie diese Struktur mal diesen Typ mal Kontakt – ist es ja noch keine Liste – es ist erst ein einzelner – Kontakt – so – also – tragt – Kontakt soll – das heißen in Schweifklammer – man was drinsteckt – soll – ?? – Leerzeichen schon geschweifte Klammer zu – und in C und C plus plus an Semikolon – aber wenn sie sind ein Teil der – Kontakt – der Nachname – offensichtlich eine Zeichenkette – Chart – wie viel Zeichen baumelt für den Nachnamen – müsste man je nach Anwendungsfall entscheiden ich habe Zimmer zweiunddreißig – ?? – will sagen ein dreißig Zeichen und die Null am Ende – Leerzeichen baumelt für den Vornamen ?? jetzt auch mal zweiunddreißig – die Telefonnummer – damit wollte extra in Versuchung führen – wenn sie dann entmachen – haben Sie auf dieser Maschine maximal – zwei dreißig tausend irgendwas – das Telefon nur bisschen mager wenn sie an Saint in – machen geht bis vierundsechzig tausend irgendwas das ist eine Telefonnummer auch mager – vor einigen haben sie nichts wie – ran – plus – vier neun – in Klammern null – und so weiter – Sie haben keine Nummern – die mit null anfangen – insofern will ich die Telefonnummer – auch zu einer Zeichenkette machen – ?? zwei zweiunddreißig – der kann man auch wirklich nach dem Motto telefonieren – ähm – so das wäre – was ich in die – sein was ich in die Datenbank als einen einzelnen Eintrag reinschreiben würde es ist nicht die Liste das ist – so wie mir nicht mal ein Eintrag das ist das Muster ?? die Schablone für einen Eintrag – das Formular sozusagen – sind nicht echte Daten – sondern ich hab erst das Formular beschrieben für einen einzigen Eintrag – daraus – baue ich jetzt – mein Telefonbuch – ?? gerade auch noch mal schreiben das man hin ich hätte gerne ein Telefonbuch – mit – zu ein paar Namen schon mal drin – Wettermueller – Anton Meyer wie auch immer wie schreiben Sie so was auf – eine ?? in dem Kontakte – sind – Kontakt – ?? bestimmtes Telefonbuch – Dame jetzt endlich die Liste – das einzelne hier ist ein Formular – zu sagen was in jedem Eintrag der Liste gespeichert wird – ist noch kein echter Eintrag sondern nur – die Form von dem Eintrag – das Telefonbuch – diese Variable soll dann nachher wirklich die Liste werden mit echten Einträgen – das was drin steht wenn sich überlegen – sollte ?? weiterschreiben Kontakt Telefonbuch – und in eckige Klammern gleich – ins – Aha – eckige Klammern – und sowas – ein Reh mit – vier Einträgen – anlegen – jeder Eintrag ist ein in das reha SA – jetzt das analoge hier – ein Telefonbuch – wenn ich hier die Zahl nicht angebe wird es Ray automatisch so groß – wie selten muss – ich lieber keine Zahl an und was lässt man irgendwelche Einträge – erst mal außen die Schweifklammer – für die – Leseinitialisierung – wurde die auf jeden Fall innen drin müsste man eigentlich in sie jetzt nicht noch mal Schweifklammer setzt nicht fix aber deutlich – übersichtlicher – wenn man drin weiter Schweifklammer setzt erster Eintrag – per Nachname Komma Vorname – Komma Telefonnummer – und ?? und der zweite Eintrag – unter Homers dritter Eintrag – ?? damit verbissen suchen können ich bastle mal gleich – fünf Einträge das Essen zum Themeprinzip sieht dass da was passiert – ?? Gates in jedem Los mit Vorname – Nachname – Nachname Vorname Telefonnummer – Vornamen Telefonnummer – was wenn man üblichen Kandidaten – Meyer mit A so – neuer – Manager und irgendeine Telefonnummer – und – dann machen meine damit die – Telefonnummer – Komma damit er spannend wird – mehrerer – aller Ausnahme da mal – Egon – der Mitte im Alphabet dahinter steht – irgendwas – an – das hatte ja schon ganz zu Beginn gesagt – dieses Sekret soll sortiert sein – wenn's nicht sortiertes würde man einmal die Sortierfunktion – drüber laufen lassen das soll sortiert sein das macht gleich die – Suche sehr effizient – tricksen dass hier müssen zusammen – ich sage einmal sollte dir zeigen die schreibersortiertes – RNA rein – wahren Leben würde man natürlich – sortieren müssen zu Fuß – müssen – die Bibliotheksfunktion – aufrufen – am – Meyer Egon käme nach Maria Carla – noch mit – Hans – Hornung und – last not least – das aber ganz am Ende Zacharias – zur Richterin Vornamen – Anton fehlt immer noch neben ABC die – so was das soll meine – Kontaktliste sein mein Telefonbuch – sein alphabetisch – sortiert – die Nachnamen sind sortiert und bei gleichen Nachnamen – sind die Vornamen – alphabetisch – sortiert – und dafür hätte ich jetzt gerne eine Suchfunktion – jemand gibt mir – ?? Nachname – Vorname – und ich möchte rausfinden was die Telefonnummer – ist schreiben Sie mal zumindest wieso eine Suchfunktion – von außen – aussehen soll – also blablablablabla – irgendwas mit runden Klammern ?? da – Schweifklammer – wir wissen nicht was drinnen steht – Schweifklammer – wie müsste diese Suchfunktion – von außen aus – anderen und Egon ?? dieselbe Telefonnummer – die eine Wohngemeinschaft – sei so – aber das Problem – ähnlicher Art was passiert wenn derselbe – Name Vorname – zweimal – oder dreimal auftritt – das ist heikel das noch mal als Kommentar – uns merken – tut du – da was passiert wenn ein Name mehrfach auftaucht – wenn die Telefonnummer – mehrfach auftaucht – ?? – okay – kein Problem dann kommt eben für den Jäger diese Telefonnummer – für den anderen dieselbe Telefonnummer – an – Komma was es in Einnahmen mehrfach auftaucht wenn ich zwei mal Egon Meyer habe – mit zwei verschiedenen Telefonnummern – ich wird das erst mal zurückstellen – das Problem – Komma dann – am Ende noch mal dazu – kommen – Gesetze davon aus jeden Namen gäbe es nur einmal – jede Kombination – Nachname Vorname – gewiss noch einmal wie selten die Suchfunktion – aus von außen – versteht hier in der obersten Zeile – richtig – ziehst nicht so gut mit Umlauten – Umlaut in der Zeichenkette – wird – dennoch akzeptieren – es passiert einfach allenfalls Blödsinn dann bei der Ausgabe je nachdem – auf welchem Gerät man es ausgibt – am – Compiler wird dieses By – nehmen aber sie haben recht es wäre – sicherer erst mal da Louis zu schreiben C – so – wie sollte die Funktion heißen – ich denke einfach nur suche – dummen einfachen Namen – von ?? auch nur noch Rückgabetyp – was kommt zurück – erster was in der Funktion gebe ich gebe der Funktion – eine Zeichenkette – für den Nachnamen – eine Zeichenkette für den Vorname – Nachname – für die Vorname – jeweils ein Zeichen geht also nicht nur ein Schar – das wäre ein Buchstabe – oder – ein Bytezahl – von null bis hundert und fünfzig oder von mindestens achtundzwanzig bis plus hundert sieben zwanzig es ist nicht ein Beistrich sondern es ist eine Zeichenkette – Wasser ja eigentlich dann ankommt – ist ja nicht die komplette Zeichenkette – sondern ist nur ein Zeiger – wo steht – die Nummer null das Zeichen Nummer null dieser Zeichenkette im Speicher das kommt ja eigentlich an es kommt nicht die komplette Zeichenkette an sondern nur – die Adresse die Hausnummer – des vordersten Zeichens der Zeichenkette – genauso hier – was ich zurückgebe – ist von derselben Sorte Musterzeichenkette – zurückgegeben werden ?? nämlich die Telefonnummer – hatte der Rückgabetyp ist nicht Schar – das wäre nur ein Zeichen ich gebe nicht nur ein Zeichen zurück – ich gebe – ein Zeiger auf eine Reihe zurück – an einzelnen Buchstaben – das ist nicht was ich zurückgeben will – ich eine Zeichenkette – zurückgeben – und C ist leider an der Stelle bisschen asymmetrisch – sie können nicht das Schreiben – das ist etwas ungeschickt – sie können aber Schreibensscharsternchen – ein Zeiger auf ein Zeichen – eigentlich ist das hier dasselbe – könnte hier statt – Schaf Vorname – Regler man auch schreiben Scharsternchen – Vornamen – ein Zeiger auf ein Zeichen – bedeutet – dasselbe an dieser Stelle hier vorne dürfen sie leider nicht die eckigen Klammern schreiben – bleibt dann nur das Jahr Sternchen – in C dürfen sie nicht da die eckigen Klammern schreiben – soll ich sag es kommt also ein Zeiger auf ein Zeichen zurück – dann – läge eine Garten schon angefangen – das mal zu Bauen wirklich schreiben Sie mal eine billige Implementierung – dafür – wie ist das ganz billig zu machen – und effizient – wenn ich nicht wüsste dass diese Liste hier – alphabetisch – sortiert ist – ich das nicht wüsste dann müsste ich auf eine sehr – uneffiziente – Weise suchen – die vielleicht erst mal hin – und dann überlegen wozu man es besser machen kann – ?? genau sie könnten hier auch X und Y schreiben – das wäre egal – es wird nur keiner mehr verstehen – als das hier Nachname Vorname steht ist für den menschlichen Leser die menschliche Leserin – nach einer Vornahme der unten hat nicht erst mal nichts mit Nachname Vorname hier oben zu tun – Punkt – das ist nur zum besseren Verständnis – dass ich hier schon diese Bezeichnung gewählt haben – Punkt die billigste Lösung wäre also eine for-Schleife – ich geh diese gesamte Liste durch – die gleich null – I kleiner Damen sie gerade gemerkt das es blöd – effizient ist denn – in den – größeren – neueren Sprachen können Sie dieses RE fragen wie viel es denn enthält – in C kann man was Zusammenhecken – mit Zeiss auf – Erden funktioniert aber – typischerweise – nicht Davos funktionieren sollte sondern nur in bestimmten Stellen jeweils außer Weise funktionieren – ich für diese einfachheitshalber – jene Variable anlegen – in der steht wie viele diesem drin sind – zwar – Kontakte – fünf – ?? andere Möglichkeit – wäre – das wäre richtig C mäßig andere Möglichkeit wäre ans Ende von diesem Gerät – einfach einen leeren Eintrag zu setzen – und dann nehmen sie keine – for-Schleife – sondern eine Hochwaldschleife – so lange bis sie auf den leeren Eintrag stoßen könnte man auch machen – das wäre schon bisschen rustikal – Zahl der Kontakte merk ich mir einfach und dann kann ich jetzt hier ?? Anzahl der Kontakte – hier erhöhen – so ich prüfe ob der Nachname – stimmt – das was im Telefonbuch – steht – an der Stelle die – Anzeige auf eine Zeichenkette – da möchte ich wissen ob das dasselbe ist – wie ich rasch ?? falschen da möchte ich wissen ob das dasselbe ist wie der Nachname – in – den größeren Sprachen können Sie das so schreiben – der aber sicher insbesondere – könnte das so schreiben – in C haben sie dagegen hier ein Zeiger und dein zeigen und vergleichen die beiden Zeiger – das wird typischerweise – schiefgehen – ?? es gibt aber die – eingebaute Funktion Stringkomper – Punkt sie – kommt er CP – die das übernimmt – die liefert eine Zahl null oder minus eins – eins null wenn die beiden gleich sind mindestens groß eins jener Reihenfolge – im Alphabet Stammestrinker – mehr da ist brauchen wir – Ring – gut – ?? – Ring – einen gewollten Sinn kommt gerade aus selber schreiben – Vorsicht wenn sie das tun wenn sie Zeichenketten – Zeichen für Zeichen vergleichen – ahnen stellen Sie sich vor – Komma das was dazwischen – scheint sich vor sie haben so eine Zeichenkette – A B C D E F und dann kommt da die abschließende – null und dann steht da Müll im Speicher – und sie haben andere Zeichenkette – ABC DF und danach steht Müll im Speicher – Punkt sie dürfen nur Zeichen für Zeichen vergleichen bis sie die null gefunden haben sie dürfen jetzt nicht alle zwei ?? dreißig Zeichen vergleichen denn nach der null – der Müll der Muster nicht derselbe sein auch wenn die Zeichenketten – eigentlich dieselben sind – muss der Müll der nach der Zeichenkette steht – nicht derselbe sein also wenn sie wirklich zu Fuß vergleichen – Zeichen für Zeichen vergleichen – dann nur bis zu der null und nicht weiter – so sicher wäre Beistrich wenn der annulliert – in – oder für was sehr schön – ich vergleiche ja nicht Telefonbuch von ihm – sondern – was der Zeichenkette für den Nachnamen steht – bestimmt auch – dann – aus dem Telefonbuch – wurde mir den Eintrag Nummer ihn – von dem Eintrag Nummer I – Punkt Versand sagte Stone mit Nachnamen – den Vergleich mit den Nachnamen der ?? übergeben worden ist das jetzt dieselben bezeichnen – es aber nur – für den menschlichen Leser – so gedacht das es hier dieselben Bezeichner sind den Compiler bringt das nicht durcheinander – dieser Nachname bezieht sich auf dieses Trakt im Telefonbuch – steht und der Nachname ist der Nachname der oben bekommt – dann – so wenn die beiden übereinstimmend – die beiden Nachnamen – übereinstimmen – Punkt – die beiden Vornamen übereinstimmte können auch zwei Hilfs ineinander schreiben – eben gesehen geht auch – die beiden Vornamen übereinstimmen – dann können wir die Telefonnummer – ganz einfach ausgeben – zurückgeben – sollte ich sagen indem wir die Telefonnummer – zurück – das wäre also aus dem Telefonbuch – selbe Stelle dann die – Telefonnummer – so – ?? ich gehe die ganze Liste durch – wenn ich einen Eintrag finde mit blassem Nachnamen passen Vornamen gebe ich die Telefonnummer – aus – sie meinte du hier das heißt wenn der Name Vorname die Kombination mehrfach vorkommt – gebe ich nur die Telefonnummer – vom allerersten aus – das ist keine so sichere Angelegenheit – professioneller – Weise erst mal gucken müssen – wie man das überhaupt hinrichten ihre Telefonnummern – auszugeben – oder man zurück liefern muss wo sich das Meer deutlich – darum geht's mir gerade nicht das Kirchmann unter den Teppich das Problem aber das bedeutet schon das man diese Funktion noch massiv um Stricken muss damit sie wirklich mit mehrfachen Namen – zurechtkommt – ?? mal davon aus das derzeit nur jeden Namen – Vornamen in der Kombination einmal gibt dann wäre das soweit richtig – was kann er passieren dass ich ihren Namen eingeben – Vornamen eingeben – der nicht im Telefonbuch – steht – das was ich komm aus der for-Schleife raus – zwischendurch – ist kein Return passiert – ich komme hier unten an – muss er natürlich jetzt dazu was zurückgeben – das wäre eine Möglichkeit das sie dann sagen nicht gefunden – haben – könnte – meistens – funktionieren – ich finde es etwas – gefährlich – man – sich vorstellen sie nutzen das zum Beispiel zum automatischen wählen – dann wird hier dann eben keine Telefonnummer gewählt sondern nicht gefunden gewählt und irgendwie fragt sich jemand auf der Gegenstelle dann – was das bedeuten sollte die Telefonnummer – Initiativen – der Stille – und so weiter – das wäre gefährlich da jetzt einfach nicht gefunden zurückzugeben – ich würde hier ?? – null zurückgeben – in C plus plus könnte man es sogar fast nur so hinschreiben – ?? null – den Nullzeiger – zu – das heißt – gerne diese Funktion verwendet – würde also prüfen müssen – kommt der Nullzeiger zurück – eines klar Obst – nicht gefunden oder kommt was anderes zurück ganz klar wir haben was gefunden – ?? würde man das typischerweise in C lösen – damit der Compiler null kennt – in all solche ?? sagen brauchen wir hier noch in Cloud Standard Dev – SPD – der Standarte finnische – so würde man das typischerweise – lösen – das Komma Kommunikation – veranstalten – Schahsternchenresultat – ist gleich – Suche – zurück mal einen existenten – erst mal – Hans – der Form – und dann suche ich danach mal gleich sofort einen den es nicht gibt – Komma – mal sehen – so in einem Schritt hier durchsuche – Mueller Hans durch – jetzt ?? ich natürlich – es hat ja schon angedroht – ein Zeiger – was zurückkommt – ist ein Zeiger auf den ersten Buchstaben – einer Zeichenkette – und netterweise zeigt jetzt erst das ist der Zeiger der Werte sei das hexadezimal – drei sechs zwei und ihr zeigt Ihnen die Entwicklungsumgebung – schon den Anfang an – da nicht zu viel Service weiter aufmachen – so – dabei Leerzeichen die Entwicklungsumgebung – schon an was denn da steht an dieser Stelle – sechs vier drei vier drei zwei – sechs vier drei vier drei zwei soweit funktioniert – der nächste Aufruf – den Namen den es nicht gibt – ?? – null wie sich das gehört – also daran würde ich es unterscheiden können – ob die Suche erfolgreich war oder nicht ?? kommt hier als Zeiger – eine null zurück der Nullzeiger – oder kommt als sei da was vernünftiges zurück so würde man die Funktion einsetzt – sie – haben recht das es ordentlich was ich hier mache dann die erfährt eine die Funktion – von Zarkontakte – und Telefonbuch – ich benutze dies ja einfach hier Zahl Kontakt und Telefonbuchpreise – als globale Variablen in der Datei vor da ist kann es ja ?? benutzen – das ist vielleicht bisschen unsauber – an was ist wenn ich mehrere Telefonbücher – haben wollen würde dann müsste ich dieser Funktion – tatsächlich sagen es ist dieses Telefonbuch – aber nicht das andere Telefonbuch – das heißt die Winzerfunktion – noch ein weiteres Ray geben – nämlich das – jeweilige Telefonbuch – Wasser angesagt ist – und – müsse man gucken oder sind recht das man hier die – Zahl der Kontakte des jeweiligen Telefonbuchs – auch noch hat – glaube an der Stelle würde ich wirklich zu der Lösung greifen – dass ich am Ende einen leeren Eintrag – noch unterbringen und nicht die Zahl der Kontakte – mit Übergeber – aus das ist doch keine saubere Geschichte – ich provoziere – hier gerade auf das Suchen – an – programmiermäßig – Software technisch ist das jedoch nicht richtig sauber eigentlich sollte diese Suchfunktion – auch offiziell erfahren aus welchem Telefonbuch – denn gesucht werden soll ich nehme jetzt ganz einfach – dreist dieses globale Telefonbuch – was davor in der Datei steht – das ist gruselig – also Suchen kommt ein Zeiger zurück – ich speichere – den Zeiger – in der variablen Resultatscharsternchen – ein Zeiger auf einen – Buchstaben – das ist nachher der Zeiger auf das vorderste – in dem Gerät rennen – wenn sie hier nur ein Schar haben – versuchen Sie diesen Zeiger hier eine Speicherstelle – die Nummer einer Speicherstelle – unterzubringen – in einer Variablen die ein Byte – speichert – und das nimmt selbst sie übel genommen hier macht – Project – May – finden Sie das dass selbst sie übernimmt – welche oft halb char Sternchenkenner – Designton – NTT oft Halbschar – Value auf Teil char Sternchen ist das was sie rechts raus kommt die Suchfunktion – liefert ein Zeiger auf einen Schar – das kommt daraus – auf deutscher Kenner Designs – kann nicht zugewiesen werden mit dem gleich weisen dazu – einen ?? Sternchen Valueanzeige – auf einen Schar auf ein Buchstaben kann nicht zugewiesen werden – einer Entität einem – Ding – einem Objekt – von der Sorte char – hier – der speichert ein Bytes – und sie weigert sich – diesen Zeiger der daraus kommt in diesem einen Bytes diesen einen Buchstaben – abzulegen – und das nächste geht dann aus demselben Grunde – weiterhin schief – warum – kommt die Anzeige raus ähm – fallen habe ich natürlich gesagt es kommt Zeiger raus – Beistrich erscheint Sternchen ?? wenn ich oben nicht char Sternchen geschrieben hätte sondern nur char – dann müsste auch hier nur Schar stehen – andererseits – wenn die oben nur char Stunde ?? char Sternchen – würde das sie wieder nicht funktionieren – dass sich die Adresse der Zeichenkette übergeben – das eine bedingt das andere – Martin – ?? mich völlig verschätzt mal sehen was er jetzt noch schaffen – an die binäre Suche – das jemals überhaupt nicht verwendet – dass diese Liste sortiert ist – als gezielt Komma das dann zumindest wie eine binäre Suche – funktionieren würde hier gehen sie wirklich jeden einzelnen durch – sie nicht wissen ob Sortiertest – das dauert heißen paar Millionen Einträge sind – ich weiß aber dass es sortiert ist – Suche – könnte man vorgeht – so das ist der Gedanke wenn ich eine sortierte Liste habe – dann guck ich in der Mitte – zuerst – bin ich zu weit in der Mitte – oder bin ich noch nicht weit genug – in der Mitte – und dann heißt das – ich muss noch in der Hälfte suchen binäre Teilung – wenn ich in der Mitte noch nicht weit genug war – Punkt ich oben weiterbilde – wieder die Mitte – bin ich da zu weit – oder – sich noch weiter – bin ich da schon zu weit bin guck ich hier weiter nachbilden – da die Mitte – und so weiter – und so weiter – ich muss ?? zu ihrem ?? gucken bei dem ich mir da gerade angucke in der Mitte ist das schon der richtige – irgendwann – wird der richtige sein – ?? sich ab ?? fortlaufende – Halbierung – das geht dann extrem schnell – er probierte das mal – wie kann man das hinschreiben – Gänsefüßchen unten – wahrscheinlich auch nicht programmiert – ich das machen würde wäre folgendes – ich würde eine Schleife bauen – die so lange läuft wie das noch nicht – gefunden worden ist – sowas wohl – gefunden – solange dies noch nicht gefunden worden – ist läuft diese Schleife – für mein wohl bauliche oben natürlich jetzt Sternsymbol – hab – so – an – ich gucke in der Mitte nach – oben ich in der Mitte – Ent – mit gleich – das muss man sich jetzt eben zusammen basteln wo man in der Mitte ist – ich kenne ja am Anfang erst mal hier die Zahl der – Kontakte der muss jetzt leider was nachlegen – das wir so noch nicht richtig sein – Punkt ich bin ganz Tag ganz brutal durch zwei teilen – dann – im Zweifelsfall bin gerade Anzahl habe bisher kein mittleres Element ?? werden nämlich eben das unter dem mittleren Element – sei so – da würde ich jetzt nachgucken – ob der größer oder kleiner ist als diese Kombination Nachname – Vorname – mithilfe von – Stringkomperstring – kommt er sagte nicht glaubt gleiches sondern sagt mit dem Vorzeichen – auch bloß als minus eins in welcher Reihenfolge – die im Alphabet stehen – das für dich ausnutzen – rein von dem Bestehen – einer Senkung der null null rauskommt wüsste ich okay – erledigt gefunden ich gebe den Wert zurück – den ich da habe die Telefonnummer Zurückdichter habe wenn austrinken wer was anders rauskommt – müsste ich jetzt anders weitersuchen – muss ist ein erstmals Kontakt Kommentare hinschreiben ?? mit Kratzer knapp – ?? – sich dann in der oberen Hälfte oder in der unteren Hälfte weitersuchen – ich müsste mir auch noch merken wo ich oben bin – wo ich unten bin was sind meine oberen und unteren Grenzen – wichtiger wäre mir jetzt folgendes – noch mal Grüße wovon – Sohn zur Notation – dieser Laufzeit – wenn ich – enden Elemente hier habe bei – der normalen Suche ein Telefonbuch – mit den Einträgen – was ist die Laufzeit – von dieser Suche im Mittel – was erwarten Sie wie viele Schritte sozusagen – diese Suchfunktion – laufen muss wenn ich in Einträge im – Telefonbuch habe – wovon ähm ✂ am richtig also im Mittel die Hälfte – bin ich immer die Liste – A vier Komma von oben nach unten durchsuche – bis ich eingefunden habe – kann ich schnell Glück haben – Anton Aal mit Doppelarm den Fini sofort – aber ich kann auch Pech haben – Herrn Zacharias am Ende den Film nicht erst ganz zuletzt – im Mittel – werde ich en halbe Schritte brauchen – um in dieser – Liste was zu finden wenn ich von oben bis unten suche – und das wäre dann O von N – und es wäre auch Ofen in Quadrat und wovon – zwei hochenden aber es wäre nicht wovon Wurzel ein – Mann würde typischerweise dafür dann O von N angeben – sind gotisch – geht das wie die erste Potenz von N – diese Suchzeit – die – mittlere Laufzeit Komplexität – ist wovon ähm – irgendwas wie en halbe Schritte dichtmachen muss – die schlimmste Laufzeit – Komplexität – muss immer bis zu Ende suchen dass es das schlimmste ist auch wovon ähm – ich eben in Schritte – bei – der binären – Suche – wenn ich fortlaufend – halbieren – was erwarten Sie da als schlimmsten – Fall wie viel Schritte muss ich machen im schlimmsten Fall ?? ich habe aus den Elementen zu suchen wie viel Schritte brauche ich im schlimmsten Fall ✂ als ich würde sagen das sind zwei der Logarithmus von N Schritte zweier Logarithmus von N Schritte – wenn sie denn verdoppeln – wenn sie die Anzahl der Elemente in der Liste verdoppeln – dann wächst der Logarithmus um eins ich brauche eine Halbierung mehr so könnte man das leicht machen oder wenn sie mit tausend vierundneunzig anfangen Beistrich bereits die Fang mit tausend zwanzig an – nach dem ersten Schritt haben sie fünf hundert zwölf zwei hundert sechsundfünfzig – hundert achtundzwanzig – vierundsechzig – und so weiter und so weiter nach neun oder zehn Schritten sind Sie fertig nach meiner Finanzierung – sind sie fertig – der zweite Logarithmus der Anzahl – könnte man auch anders schreiben wenn es um rechnen ist zum Beispiel der Zehnerlogarithmus – von N durch den Zehnerlogarithmus – von zwei – es ist ein auch relativ egal es ist of von – Lok ähm so würde man das typischerweise – bezeichnen O von Boken egal welcher Logarithmusalgorithmen – unterscheiden sich enorm konstante Faktoren sind jeder zwei ?? wird muss – stattdessen bis auf den Zehnerlogarithmus – nehmen und durch die CD-ROMs von zwei Teilen – egal welchen Logarithmus hier nehme – wovon Lok N würde man dazu sagen – das ist – deutlich schneller – für große N deutlich schneller als wovon ähm die lineare Suche von Anfang bis Ende – so wird man typischerweise – mindestens Vorgehen in Datenbanken – wird auch noch Indices haben – und Ähnliches – aber das ist das aller mindeste was man machen würde ✂ Bemerkung froh von Lot N wäre automatisch – dann auch O von N und O von N Quadrat und O von zwei hoch ähm – aus mathematisch – ist das hier eine echte Teilmenge – von O von N und eine echt dass eine echte Teilmenge von O von zum Beispiel zwei hoch ähm – dieses groß O sagt ja – alle Funktionen – die maximal – so schlimm sind Asymptote Speedy Funktion die in den runden Klammern steht – also wenn etwas offener Kern ist es automatisch auffangen – wovon zwei Hochent aber das Ding hier eben die lineare Suche die ist definitiv – nichts – sie ist Element O von N von der Laufzeitkapazität – aber sie ist nicht Element O von Lok ähm – sie ist schlimmer – als das sie nicht – und jedoch noch – der Vollständigkeit – halber die Videosuche – ausformuliert – ich merke mir für jeden Durchgang – die Nummer des Elements bei dem ich anfange zu suchen und die Nummer des Elements werde mich aufhört – zu suchen also erst mal von null bis Gesamtzahl minus eins – alle – und dann ist dies jetzt eine Endlosschleife – geworden – in der ich fortlaufend halbieren – dass es deshalb ihren Anfang und Ende durch zwei – Ärzte wird in der Mitte pädagogisch nach ist der Wert in der Mitte zu groß oder zu klein ?? wird in der Mitte vergleiche – ich – mit dem übergebenen Nachnamen vornahm – wenn der Wert in der Mitte kleiner – ist – als die übergebene Nachname Vorname bin also vorher im Alphabet steht – dann suche ich in der zweiten – Hälfte weiter – setze den Anfang auf Mitte plus eins – damit zurück in der zweiten Hälfte weiter – und – wenn der Name in der Mitte – Kurz ihn – in der Name in der Mitte – hinter – dem übergebenen Namen steht im Alphabet – dann mach ich mit dem Anfang – der vorderen Hälfte meiner Liste weiter setzt das Ende auch mit minus eins – Vergleich – mit String Konversion – Komma – zählen hier wieso diese drei Vergleiche stattfinden – im ersten ?? will ich wissen ob der Name Telefonbuch – in der Mitte – im Alphabet – vor – dem übergebenen Namen ist – ist der Nachname – vor dem übergebenen Namen – oder – Stimmen Nachname – und Nachname über ein – selben Nachnamen – und dann prüfe ich die Vornamen – ob der – Vorname – den ich in der Mitte gefunden habe im Alphabet vor dem – übergebenen Vornamen steht – entweder – das erste passiert noch das zweite passiert – noch eine Möglichkeit – Nachname und Vorname – stimmen – angeblich direkt die Telefonnummer zurück – irgendwann muss diese for-Schleife ja mal abbrechen wenn es schief geht – das macht diese letzte Bedingung hier dann endet die Wahl schlafe das ist die Klammer auf von der Warteschleife damit wieder zu – ?? – wenn ich hier das Ende auf Mitte Minuseinsätze – minus eins – wenn ich ganz am Ende – unter den Anfang runtergehen – das ist nicht mehr erfüllt – und wenn ich hier den Anfang auch mit dem Bus einsetze – wenn ich ganz am Ende – über das Ende – hinausgehen – das es auch nicht mehr erfüllt und in dem Fall kann ich dann einfach sagen Terminal ich habe nichts gefunden – das heißt es sieht eher so aus wie eine Endlosschleife – die – wie sieht es aus wie ein Endlosschleife – aber das ist mal wieder – mit mehreren versteckten Müttern garniert diese Schleife wird ähm – und es gibt eine technische Randbemerkung – wenn ich die Mitte bestimme – das ist klassischer Fehler – wenn ich die Mittelstimme – ist das wie ich das hier mache eine schlechte Idee – eine große Zahl noch eine große Zahl diese Summe kann überlaufen – und anteilig Blödsinn durch zwei – hier muss man vorsichtig sein das sollte man anders machen – ich hab jetzt so hin – ?? Claus was ich meine – das ist aber nicht die professionellen