{"id":2374,"date":"2019-12-08T23:26:56","date_gmt":"2019-12-08T20:26:56","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2374"},"modified":"2024-12-16T22:32:32","modified_gmt":"2024-12-16T19:32:32","slug":"binary-search","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/de\/2019\/12\/08\/binary-search\/","title":{"rendered":"Bin\u00e4re Suche"},"content":{"rendered":"

Angenommen, wir m\u00fcssen herausfinden, ob die E-Mail-Adresse \u201edemensdeum@gmail.com<\/a>\u201c in der Liste der zul\u00e4ssigen E-Mail-Adressen f\u00fcr den Empfang von Briefen enthalten ist .<\/p>\n

Lassen Sie uns die gesamte Liste vom ersten bis zum letzten Element durchgehen und pr\u00fcfen, ob das Element mit der angegebenen Adresse \u00fcbereinstimmt – Lassen Sie uns einen linearen Suchalgorithmus implementieren. Aber das wird lange dauern, oder nicht?<\/p>\n

Um diese Frage zu beantworten, verwenden Sie die \u201eZeitkomplexit\u00e4t von Algorithmen\u201c, \u201eO\u201c-Notation. Die Betriebszeit der linearen Suche entspricht im schlimmsten Fall der n-ten Anzahl von Array-Elementen. Schreiben wir dies in \u201eO\u201c-Notation – An). Als n\u00e4chstes m\u00fcssen wir erkl\u00e4ren, dass es f\u00fcr jeden bekannten Algorithmus drei Leistungsindikatoren gibt: Best-Case-, Worst-Case- und Average-Case-Ausf\u00fchrungszeiten. Befindet sich beispielsweise die E-Mail-Adresse \u201edemensdeum@gmail.com<\/a>\u201c im ersten Index des Arrays, wird sie im ersten Schritt von gefunden F\u00fcr den Algorithmus folgt daraus, dass die Ausf\u00fchrungszeit bestenfalls – O(1); und wenn am Ende der Liste, dann ist dies der schlimmste Fall – O(n)<\/p>\n

\"\"<\/a><\/p>\n

Aber was ist mit den Details der Software-Implementierung und der Hardware-Leistung? Sie sollten einen gro\u00dfen Einfluss auf das O haben? Atmen Sie nun ein und stellen Sie sich vor, dass die Berechnung der Zeitkomplexit\u00e4t f\u00fcr eine abstrakte ideale Maschine berechnet wird, in der es nur diesen Algorithmus und sonst nichts gibt.<\/p>\n

Algorithmus<\/h3>\n

Okay, es stellt sich heraus, dass die lineare Suche ziemlich langsam ist. Versuchen wir es mit der bin\u00e4ren Suche. Zun\u00e4chst sollte klargestellt werden, dass wir nicht mit Bin\u00e4rdaten arbeiten; dieser Name wurde dieser Methode aufgrund der Besonderheiten ihrer Arbeit gegeben. Zun\u00e4chst sortieren wir das Array nach lexikografische Reihenfolge<\/a>, dann nimmt der Algorithmus den Bereich des gesamten Arrays, ruft das mittlere Element des Bereichs ab und vergleicht es lexikographisch<\/a> und abh\u00e4ngig vom Ergebnis des Vergleichs entscheidet, welcher Bereich f\u00fcr die weitere Suche verwendet werden soll – die obere H\u00e4lfte des Stroms oder die untere. Das hei\u00dft, bei jedem Suchschritt wird eine Entscheidung aus zwei m\u00f6glichen – Bin\u00e4re Logik. Dieser Schritt wird wiederholt, bis entweder das Wort gefunden wird oder nicht (der Schnittpunkt des unteren und oberen Index des Bereichs tritt auf).<\/p>\n

Leistung dieses Algorithmus – Der beste Fall ist, wenn ein Element sofort in der Mitte des Arrays O(1) gefunden wird, der schlechteste Fall der Aufz\u00e4hlung ist O(log n)<\/p>\n

Fallstricke<\/h3>\n

Bei der Implementierung der bin\u00e4ren Suche bin ich nicht nur auf das interessante Problem der fehlenden Standardisierung des lexikografischen Vergleichs<\/b> in Programmiersprachenbibliotheken gesto\u00dfen, sondern habe sogar festgestellt, dass es keinen einheitlichen Standard f\u00fcr die Implementierung gibt localeCompare innerhalb von JavaScript<\/b>. Der ECMAScript-Standard erlaubt unterschiedliche Implementierungen dieser Funktion, weshalb beim Sortieren mit localeCompare auf verschiedenen JavaScript-Engines v\u00f6llig unterschiedliche Ergebnisse beobachtet werden k\u00f6nnen.<\/p>\n

Damit der Algorithmus korrekt funktioniert, ist es notwendig, nur denselben lexikografischen Vergleichsalgorithmus zu sortieren und zu verwenden<\/b>, andernfalls funktioniert nichts. Co-aber wenn Sie beispielsweise versuchen, ein Array in Scala zu sortieren und mit NodeJS zu suchen, ohne Ihre eigene Sortierung\/Sortierung einer Implementierung zu implementieren, dann erwartet Sie nichts au\u00dfer Entt\u00e4uschung \u00fcber die Menschheit.<\/p>\n

Quellen<\/h3>\n

Was ist ein lexikografischer Vergleich und was stellt er dar?<\/a>
\u041f\u043e\u0447\u0435\u043c\u0443 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f log N \u0432\u043c\u0435\u0441\u0442\u043e lb N?<\/a>
\n\u0414\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/a>
\n\u0417\u043d\u0430\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432<\/a>
\nhttps:\/\/stackoverflow.com\/questions\/52941016\/sorting-in-localecompare-in-javascript<\/a><\/p>\n

Quellcode<\/h3>\n

https:\/\/gitlab.com\/demensdeum\/algorithms<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Angenommen, wir m\u00fcssen herausfinden, ob die E-Mail-Adresse \u201edemensdeum@gmail.com\u201c in der Liste der zul\u00e4ssigen E-Mail-Adressen f\u00fcr den Empfang von Briefen enthalten ist . Lassen Sie uns die gesamte Liste vom ersten bis zum letzten Element durchgehen und pr\u00fcfen, ob das Element mit der angegebenen Adresse \u00fcbereinstimmt – Lassen Sie uns einen linearen Suchalgorithmus implementieren. Aber dasContinue reading “Bin\u00e4re Suche”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,132],"class_list":["post-2374","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-binary-search","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"de","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/comments?post=2374"}],"version-history":[{"count":19,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2374\/revisions"}],"predecessor-version":[{"id":3931,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2374\/revisions\/3931"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/media?parent=2374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/categories?post=2374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/tags?post=2374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}