LinkedList<\/code> bin\u00e4r zu suchen?<\/li>\n<\/ul>\n\n\n\nDen Code zum Artikel findest du in diesem GitHub-Repository<\/a>.<\/p>\n\n\n\n\n\nBin\u00e4re Suche \u2013 ein Beispiel<\/h2>\n\n\n\n
Wenn wir fr\u00fcher ein unbekanntes Wort \u00fcbersetzen wollten, hatten wir daf\u00fcr keine App, sondern mussten dieses in einem W\u00f6rterbuch nachschlagen. Theoretisch k\u00f6nnte man nun von vorne nach hinten jede Seite von links oben nach rechts unten nach dem gew\u00fcnschten Wort durchsuchen.<\/p>\n\n\n\n
Mit etwas Gl\u00fcck finden wir das Wort auf den ersten Seiten des Buches. Wenn wir Pech haben, finden wir es erst gegen Ende des Buches \u2013 oder gar nicht (das w\u00fcrden wir erst auf der allerletzten Seite feststellen). Auch bei relativ weit vorne liegenden W\u00f6rtern (wie z. B. \"Bin\u00e4rsuche\") m\u00fcssten wir so ziemlich lange suchen.<\/p>\n\n\n\n
Diese Vorgehensweise nennt sich \"lineare Suche\". Das folgende Bild zeigt ein vereinfachtes Beispiel mit Zahlen statt W\u00f6rtern. Gesucht werden soll die Position der Zahl 61 im dargestellten Array.<\/p>\n\n\n
\n![\"Lineare](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/linear-search-example-v3-800x323.png\")
Lineare Suche in einem Zahlen-Array<\/figcaption><\/figure>\n<\/div>\n\n\nIn diesem vereinfachten Beispiel ben\u00f6tigen wir sechs Schritte, um die 61 zu finden.<\/p>\n\n\n\n
Nat\u00fcrlich w\u00fcrde in einem W\u00f6rterbuch niemand auf diese Weise suchen. Stattdessen schlagen wir das Buch ungef\u00e4hr in der Mitte auf und schauen, ob das Wort alphabetisch davor oder danach einzuordnen ist. Wir wissen somit, in welcher H\u00e4lfte des Buchs sich das Wort befindet und k\u00f6nnen die andere H\u00e4lfte ignorieren. Danach suchen wir wieder die Mitte und schr\u00e4nken den Suchbereich erneut auf die H\u00e4lfte (also insgesamt ein Viertel) ein. Mit jedem weiteren Suchschritt halbieren wir die Anzahl der verbleibenden Seiten. Auf diese Weise kommen wir in relativ wenigen Schritten zur Zielseite \u2013 und auf der Zielseite zum gesuchten Wort.<\/p>\n\n\n\n
Das nennt sich dann \"bin\u00e4re Suche\". Das folgende Bild macht deutlich, dass die Suche so wesentlich schneller zum Ergebnis f\u00fchrt als die lineare Suche:<\/p>\n\n\n
\n![\"Bin\u00e4re](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-search-example-v3-800x236.png\")
Bin\u00e4re Suche in einem Zahlen-Array<\/figcaption><\/figure>\n<\/div>\n\n\nMit der Bin\u00e4rsuche brauchen wir lediglich drei Schritte:<\/p>\n\n\n\n
\n- Im ersten Schritt vergleichen wir den gesuchten Wert 61 mit dem mittleren Element 36. Der gesuchte Wert ist gr\u00f6\u00dfer, muss sich also rechts von der 36 befinden.<\/li>\n\n\n\n
- Im zweiten Schritt vergleichen wir die 61 mit dem mittleren Element des rechten Bereichs, der 79. Der gesucht Wert ist kleiner, muss sich also links von der 79 befinden.<\/li>\n\n\n\n
- Zwischen 36 und 79 befindet sich nur noch ein Element. Auch dieses m\u00fcssen wir noch einmal mit dem gesuchten Element vergleichen. In diesem Beispiel haben wir das gesuchte Element 61 gefunden. Hier h\u00e4tte sich aber auch eine andere Zahl zwischen 36 und 79 befinden k\u00f6nnen. Das h\u00e4tte bedeutet, dass das Array gar keine 61 enth\u00e4lt.<\/li>\n<\/ol>\n\n\n\n
Die Bin\u00e4rsuche macht selbstverst\u00e4ndlich nur dann Sinn, wenn die W\u00f6rter im W\u00f6rterbuch (so wie die Zahlen im Beispiel) sortiert sind. W\u00fcrden die W\u00f6rter in zuf\u00e4lliger Reihenfolge abgedruckt sein, bliebe uns nichts anderes \u00fcbrig als Wort f\u00fcr Wort \u2013 also linear \u2013 zu suchen.<\/p>\n\n\n\n
Bin\u00e4re Suche \u2013 Pseudocode<\/h2>\n\n\n\n
Im folgenden Pseudocode bezeichnen wir das gesuchte Element mit \"Schl\u00fcssel\" (im Englischen wird es mit \"key\" bezeichnet).<\/p>\n\n\n\n
\n- Bestimme die mittlere Position des zu durchsuchenden Bereichs des Arrays.<\/li>\n\n\n\n
- Lese das Element an der mittleren Position.<\/li>\n\n\n\n
- Vergleiche den Schl\u00fcssel mit dem mittleren Element:\n
\n- Ist der Schl\u00fcssel gleich<\/em> dem mittleren Element, dann haben wir das Ziel erreicht. Gebe die mittlere Position als Ergebnis zur\u00fcck.<\/li>\n\n\n\n
- Ist der Schl\u00fcssel kleiner<\/em> als das mittlere Element, dann f\u00fchre die Bin\u00e4rsuche im Teilarray links<\/em> von der mittleren Position aus. Es sei denn, dieses Teilarray hat die L\u00e4nge 0, dann ist die Suche ohne Ergebnis beendet.<\/li>\n\n\n\n
- Ist der Schl\u00fcssel gr\u00f6\u00dfer<\/em> als das mittlere Element, dann f\u00fchre die Bin\u00e4rsuche im Teilarray rechts<\/em> von der mittleren Position aus. Es sei denn, dieses Teilarray hat die L\u00e4nge 0, dann ist die Suche ohne Ergebnis beendet.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
Implementierung von bin\u00e4rer Suche in Java<\/h2>\n\n\n\n
Die Bin\u00e4rsuche kann rekursiv oder iterativ implementiert werden.<\/p>\n\n\n\n
Bin\u00e4re Suche rekursiv<\/h3>\n\n\n\n
Die Pseudocode f\u00fcr die bin\u00e4re Suche aus dem vorherigen Kapitel legt eine rekursive Implementierung nahe.<\/p>\n\n\n\n
Die rekursive Implementierung in Java f\u00fcr ein Array von int<\/code>-Primitiven sieht wie folgt aus:<\/p>\n\n\npublic<\/span> static<\/span> int<\/span> binarySearchRecursively<\/span>(int<\/span>[] array, int<\/span> key)<\/span> <\/span>{\n return<\/span> binarySearchRecursively(array, 0<\/span>, array.length, key);\n}\n\npublic<\/span> static<\/span> int<\/span> binarySearchRecursively<\/span>(\n int<\/span>[] array, int<\/span> fromIndex, int<\/span> toIndex, int<\/span> key)<\/span> <\/span>{\n if<\/span> (toIndex <= fromIndex) return<\/span> -1<\/span>;\n\n int<\/span> mid = (fromIndex + toIndex) >>> 1<\/span>;\n int<\/span> midVal = array[mid];\n\n if<\/span> (key == midVal) {\n return<\/span> mid;\n } else<\/span> if<\/span> (key < midVal) {\n return<\/span> binarySearchRecursively(array, fromIndex, mid, key);\n } else<\/span> {\n return<\/span> binarySearchRecursively(array, mid + 1<\/span>, toIndex, key);\n }\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nDen Code findest du im GitHub-Repository in der Klasse BinarySearch ab Zeile 12<\/a>. Passende Unit-Tests dazu gibt es in BinarySearchTest<\/a>.<\/p>\n\n\n\nWichtig ist hierbei die mittlere Position mid<\/code> mittels \"unsigned right shift\" zu berechnen: <\/p>\n\n\n\nint mid = (fromIndex + toIndex) >>> 1 <\/code><\/p>\n\n\n\nUnd nicht wie folgt:<\/p>\n\n\n\n
int mid = (fromIndex + toIndex) \/ 2<\/code><\/p>\n\n\n\nF\u00fcr den Fall dass die Summe gr\u00f6\u00dfer ist als Integer.MAX_VALUE<\/code>, w\u00fcrde die zweite Variante zu einem Overflow bzw. einem \"Roll Over\" f\u00fchren, und das Ergebnis w\u00e4re eine negative Zahl. <\/p>\n\n\n\nOhne den >>><\/code>-Operator w\u00e4re auch folgender Weg korrekt:<\/p>\n\n\n\nint mid = fromIndex + (toIndex - fromIndex) \/ 2;<\/code><\/p>\n\n\n\nAber das ist l\u00e4ngst nicht so cool ;-)<\/p>\n\n\n\n
Bin\u00e4re Suche iterativ<\/h3>\n\n\n\n
Rekursion ben\u00f6tigt zus\u00e4tzliche CPU-Zyklen und zus\u00e4tzlichen Speicherplatz auf dem Heap. Daher sind iterative Implementierungen in der Regel vorzuziehen. <\/p>\n\n\n\n
Die entsprechende iterative Java-Implementierung f\u00fcr ein int<\/code>-Array sieht wie folgt aus:<\/p>\n\n\npublic<\/span> static<\/span> int<\/span> binarySearchIteratively<\/span>(int<\/span>[] array, int<\/span> key)<\/span> <\/span>{\n return<\/span> binarySearchIteratively(array, 0<\/span>, array.length, key);\n}\n\npublic<\/span> static<\/span> int<\/span> binarySearchIteratively<\/span>(\n int<\/span>[] array, int<\/span> fromIndex, int<\/span> toIndex, int<\/span> key)<\/span> <\/span>{\n int<\/span> low = fromIndex;\n int<\/span> high = toIndex;\n\n while<\/span> (low < high) {\n int<\/span> mid = (low + high) >>> 1<\/span>;\n int<\/span> midVal = array[mid];\n\n if<\/span> (key == midVal) {\n return<\/span> mid;\n } else<\/span> if<\/span> (key < midVal) {\n high = mid;\n } else<\/span> {\n low = mid + 1<\/span>;\n }\n }\n\n return<\/span> -1<\/span>;\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nDie Variablen low<\/code> und high<\/code> sind hier nicht zwingend erforderlich. Man k\u00f6nnte innerhalb der while<\/code>-Schleife auch fromIndex<\/code> und toIndex<\/code> ver\u00e4ndern. Methodenparameter zu \u00e4ndern gilt jedoch in der Regel als unsauberes Design.<\/p>\n\n\n\nAuch diesen Code findest du in der Klasse BinarySearch ab Zeile 52<\/a>. Die Unit-Tests in BinarySearchTest ab Zeile 64<\/a>.<\/p>\n\n\n\nBin\u00e4re Suche im JDK<\/h2>\n\n\n\n
Bin\u00e4re Suche in Arrays m\u00fcssen wir nat\u00fcrlich nicht selbst implementieren. Das JDK bietet bereits entsprechende Methoden f\u00fcr Arrays aller primitiven Datentypen und f\u00fcr Objekt-Arrays in der java.util.Arrays<\/code>-Klasse. Au\u00dferdem bietet es eine Methode f\u00fcr die Bin\u00e4rsuche in Listen in der java.util.Collections<\/code>-Klasse.<\/p>\n\n\n\nArrays.binarySearch()<\/h3>\n\n\n\n
In einem int<\/code>-Array k\u00f6nnen wir beispielsweise wie folgt suchen:<\/p>\n\n\nint<\/span>[] array = new<\/span> int<\/span>[] {10<\/span>, 19<\/span>, 23<\/span>, 25<\/span>, 36<\/span>, 61<\/span>, 79<\/span>, 81<\/span>, 99<\/span>};\nint<\/span> posOf36 = Arrays.binarySearch(array, 36<\/span>);<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nCollections.binarySearch()<\/h3>\n\n\n\n
In einer entsprechenden ArrayList<\/code> von Integer<\/code>-Objekten k\u00f6nnen wir wie folgt suchen:<\/p>\n\n\nList<Integer> list = new<\/span> ArrayList<>(List.of(10<\/span>, 19<\/span>, 23<\/span>, 25<\/span>, 36<\/span>, 61<\/span>, 79<\/span>, 81<\/span>, 99<\/span>));\nint<\/span> posOf36 = Collections.binarySearch(list, 36<\/span>);<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nAchtung: Die Methode Collections.binarySearch()<\/code> kann f\u00fcr jede Klasse aufgerufen werden, die das List<\/code>-Interface implementiert. Also beispielsweise auch f\u00fcr LinkedList<\/code>.<\/p>\n\n\n\nIn einer verketteten Liste kann allerdings nicht direkt, sondern nur per Iteration auf ein bestimmtes Element zugegriffen werden, womit wir (fast) wieder bei der linearen Suche angekommen sind. Mehr dazu \u2013 und warum die Bin\u00e4rsuche auf einer LinkedList<\/code> dennoch sinnvoll sein kann \u2013 erf\u00e4hrst du im n\u00e4chsten Kapitel.<\/p>\n\n\n\nZeitkomplexit\u00e4t von bin\u00e4rer Suche<\/h2>\n\n\n\n
Bei der bin\u00e4ren Suche halbieren wir mit jedem Suchschritt die Anzahl der noch zu durchsuchenden Eintr\u00e4ge. Oder anders herum: wenn sich die Anzahl der Eintr\u00e4ge verdoppelt, brauchen wir nur einen Suchschritt mehr.<\/p>\n\n\n\n
Dies entspricht logarithmischem Aufwand, also O(log n)<\/em>.<\/p>\n\n\n\nMehr \u00fcber die O- (bzw. Landau-) Notation erf\u00e4hrst du hier: O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a><\/p>\n\n\n