powered by 
Du schreibst Funktionen, die in Listen suchen: von vorn, von hinten, nach der kleinsten Zahl, und in sortierten Listen durch Halbieren, so schnell, dass hunderttausend Suchen in hunderttausend Zahlen nur einen Augenblick dauern.
Die einfachste Suche schaut sich ein Element nach dem anderen an, bis sie es gefunden hat. Bei einer Liste mit einer Million Zahlen sind das im schlimmsten Fall eine Million Vergleiche. Ist die Liste sortiert, geht es anders: Schau in die Mitte, und du weißt, in welcher Hälfte die Zahl stehen muss. Nach dem nächsten Blick ist es ein Viertel, dann ein Achtel. Nach 20 Blicken ist von einer Million nur noch eine Zahl übrig, denn 2²⁰ ist mehr als eine Million.
numbers = [2, 5, 8, 12, 16, 23] low = 0 high = numbers.length - 1 middle = (low + high) / 2 # 2: numbers[2] ist 8
Bei ganzen Zahlen rundet / ab: Die Mitte zwischen den Indizes 0 und 5 ist 2.
numbers = [2, 5, 8, 12, 16, 23] low = 0 high = len(numbers) - 1 middle = (low + high) // 2 # 2: numbers[2] ist 8
// teilt und rundet ab: Die Mitte zwischen den Indizes 0 und 5 ist 2.
const numbers = [2, 5, 8, 12, 16, 23]; let low = 0; let high = numbers.length - 1; const middle = Math.floor((low + high) / 2); // 2: numbers[2] ist 8
Math.floor rundet ab: Die Mitte zwischen den Indizes 0 und 5 ist 2.
Wer findet, gibt den Index zurück; wer nichts findet, sagt das mit
nil.
None.
null.
Schreib eine Funktion linear_search(items, wanted), die den Index zurückgibt, an dem wanted zum ersten Mal in der Liste steht, und nil, wenn es nicht darin steht: linear_search([4, 8, 15, 8], 8) ergibt 1. Mit einer Schleife, ohne index.
Wie contains aus den Listen, nur gibst du den Index zurück. items.each_with_index do |item, i| … end gibt dir beides.
Schreib eine Funktion linear_search(items, wanted), die den Index zurückgibt, an dem wanted zum ersten Mal in der Liste steht, und None, wenn es nicht darin steht: linear_search([4, 8, 15, 8], 8) ergibt 1. Mit einer Schleife, ohne index.
Wie contains aus den Listen, nur gibst du den Index zurück. for i in range(len(items)): zählt die Indizes durch.
Schreib eine Funktion linearSearch(items, wanted), die den Index zurückgibt, an dem wanted zum ersten Mal in der Liste steht, und null, wenn es nicht darin steht: linearSearch([4, 8, 15, 8], 8) ergibt 1. Mit einer Schleife, ohne indexOf und findIndex.
Wie contains aus den Listen, nur gibst du den Index zurück. for (let i = 0; i < items.length; i++) zählt die Indizes durch.
Schreib eine Funktion min_index(numbers), die den Index der kleinsten Zahl zurückgibt; kommt sie mehrmals vor, den ersten: min_index([5, 2, 9, 2]) ergibt 1. Die Liste ist nie leer. Ohne min und index.
Wie die größte Zahl aus den Listen, nur merkst du dir den Index statt der Zahl: best fängt bei 0 an, und du vergleichst numbers[i] mit numbers[best].
Schreib eine Funktion min_index(numbers), die den Index der kleinsten Zahl zurückgibt; kommt sie mehrmals vor, den ersten: min_index([5, 2, 9, 2]) ergibt 1. Die Liste ist nie leer. Ohne min und index.
Wie die größte Zahl aus den Listen, nur merkst du dir den Index statt der Zahl: best fängt bei 0 an, und du vergleichst numbers[i] mit numbers[best].
Schreib eine Funktion minIndex(numbers), die den Index der kleinsten Zahl zurückgibt; kommt sie mehrmals vor, den ersten: minIndex([5, 2, 9, 2]) ergibt 1. Die Liste ist nie leer. Ohne Math.min und indexOf.
Wie die größte Zahl aus den Listen, nur merkst du dir den Index statt der Zahl: best fängt bei 0 an, und du vergleichst numbers[i] mit numbers[best].
Schreib eine Funktion last_index(items, wanted), die den Index zurückgibt, an dem wanted zum letzten Mal steht, und nil, wenn es nicht darin steht: last_index([4, 8, 15, 8], 8) ergibt 3. Such von hinten, dann bist du beim ersten Fund fertig. Ohne rindex.
Zähl vom letzten Index, items.length - 1, herunter bis 0, wie bei der Liste rückwärts.
Schreib eine Funktion last_index(items, wanted), die den Index zurückgibt, an dem wanted zum letzten Mal steht, und None, wenn es nicht darin steht: last_index([4, 8, 15, 8], 8) ergibt 3. Such von hinten, dann bist du beim ersten Fund fertig. Ohne index.
Zähl vom letzten Index herunter bis 0: range(len(items) - 1, -1, -1).
Schreib eine Funktion lastIndex(items, wanted), die den Index zurückgibt, an dem wanted zum letzten Mal steht, und null, wenn es nicht darin steht: lastIndex([4, 8, 15, 8], 8) ergibt 3. Such von hinten, dann bist du beim ersten Fund fertig. Ohne lastIndexOf.
Zähl vom letzten Index, items.length - 1, herunter bis 0.
Die Temperaturen eines Tages stehen in einer Liste, eine je Stunde. Schreib eine Funktion first_greater(numbers, limit), die den Index der ersten zurückgibt, die über limit liegt, und nil, wenn keine es tut: first_greater([12, 15, 21, 25, 19], 20) ergibt 2.
Wie die lineare Suche, nur fragst du nicht nach Gleichheit, sondern ob die Zahl größer ist.
Die Temperaturen eines Tages stehen in einer Liste, eine je Stunde. Schreib eine Funktion first_greater(numbers, limit), die den Index der ersten zurückgibt, die über limit liegt, und None, wenn keine es tut: first_greater([12, 15, 21, 25, 19], 20) ergibt 2.
Wie die lineare Suche, nur fragst du nicht nach Gleichheit, sondern ob die Zahl größer ist.
Die Temperaturen eines Tages stehen in einer Liste, eine je Stunde. Schreib eine Funktion firstGreater(numbers, limit), die den Index der ersten zurückgibt, die über limit liegt, und null, wenn keine es tut: firstGreater([12, 15, 21, 25, 19], 20) ergibt 2.
Wie die lineare Suche, nur fragst du nicht nach Gleichheit, sondern ob die Zahl größer ist.
In einer sortierten Liste geht es schneller: Schau in die Mitte. Ist die Zahl dort kleiner als die gesuchte, kann diese nur rechts davon stehen, sonst links; so halbierst du den Bereich, bis du sie hast oder er leer ist. Schreib binary_search(numbers, wanted) für eine aufsteigend sortierte Liste verschiedener Zahlen: der Index oder nil. binary_search([2, 5, 8, 12, 16, 23], 12) ergibt 3. Ohne index und bsearch.
Zwei Zahlen grenzen den Bereich ein, in dem die gesuchte noch stehen kann: low = 0 und high = numbers.length - 1. Die Mitte ist (low + high) / 2.
Ist numbers[middle] zu klein, rückt low hinter die Mitte, ist sie zu groß, rückt high davor. Solange low <= high, ist noch etwas übrig.
In einer sortierten Liste geht es schneller: Schau in die Mitte. Ist die Zahl dort kleiner als die gesuchte, kann diese nur rechts davon stehen, sonst links; so halbierst du den Bereich, bis du sie hast oder er leer ist. Schreib binary_search(numbers, wanted) für eine aufsteigend sortierte Liste verschiedener Zahlen: der Index oder None. binary_search([2, 5, 8, 12, 16, 23], 12) ergibt 3. Ohne index und bisect.
Zwei Zahlen grenzen den Bereich ein, in dem die gesuchte noch stehen kann: low = 0 und high = len(numbers) - 1. Die Mitte ist (low + high) // 2.
Ist numbers[middle] zu klein, rückt low hinter die Mitte, ist sie zu groß, rückt high davor. Solange low <= high, ist noch etwas übrig.
In einer sortierten Liste geht es schneller: Schau in die Mitte. Ist die Zahl dort kleiner als die gesuchte, kann diese nur rechts davon stehen, sonst links; so halbierst du den Bereich, bis du sie hast oder er leer ist. Schreib binarySearch(numbers, wanted) für eine aufsteigend sortierte Liste verschiedener Zahlen: der Index oder null. binarySearch([2, 5, 8, 12, 16, 23], 12) ergibt 3. Ohne indexOf.
Zwei Zahlen grenzen den Bereich ein, in dem die gesuchte noch stehen kann: low = 0 und high = numbers.length - 1. Die Mitte ist Math.floor((low + high) / 2).
Ist numbers[middle] zu klein, rückt low hinter die Mitte, ist sie zu groß, rückt high davor. Solange low <= high, ist noch etwas übrig.
Jemand denkt sich eine Zahl von low bis high, du rätst, und es heißt »größer« oder »kleiner«. Geschickt rät man immer die Mitte, abgerundet. Schreib guesses(secret, low, high), die die Liste deiner Tipps zurückgibt, bis du secret triffst: guesses(7, 1, 10) ergibt [5, 8, 6, 7].
Wie die binäre Suche, nur ohne Liste: Der Bereich ist von low bis high, die Mitte dein Tipp.
Jemand denkt sich eine Zahl von low bis high, du rätst, und es heißt »größer« oder »kleiner«. Geschickt rät man immer die Mitte, abgerundet. Schreib guesses(secret, low, high), die die Liste deiner Tipps zurückgibt, bis du secret triffst: guesses(7, 1, 10) ergibt [5, 8, 6, 7].
Wie die binäre Suche, nur ohne Liste: Der Bereich ist von low bis high, die Mitte dein Tipp.
Jemand denkt sich eine Zahl von low bis high, du rätst, und es heißt »größer« oder »kleiner«. Geschickt rät man immer die Mitte, abgerundet. Schreib guesses(secret, low, high), die die Liste deiner Tipps zurückgibt, bis du secret triffst: guesses(7, 1, 10) ergibt [5, 8, 6, 7].
Wie die binäre Suche, nur ohne Liste: Der Bereich ist von low bis high, die Mitte dein Tipp.
In einer aufsteigend sortierten Liste stehen erst alle Zahlen unter limit, dann alle ab limit. Schreib first_at_least(numbers, limit), die den ersten Index ab limit zurückgibt, und die Länge der Liste, wenn keine Zahl so groß ist: first_at_least([1, 3, 3, 5, 8], 3) ergibt 1. Mit Halbieren: Bleib bei zwei Grenzen, bis sie sich treffen.
Die Antwort liegt zwischen low = 0 und high = numbers.length. Ist die Zahl in der Mitte kleiner als limit, liegt die Antwort rechts davon; sonst kann es die Mitte selbst sein: high = middle.
Wenn low und high gleich sind, ist das die Antwort.
In einer aufsteigend sortierten Liste stehen erst alle Zahlen unter limit, dann alle ab limit. Schreib first_at_least(numbers, limit), die den ersten Index ab limit zurückgibt, und die Länge der Liste, wenn keine Zahl so groß ist: first_at_least([1, 3, 3, 5, 8], 3) ergibt 1. Mit Halbieren: Bleib bei zwei Grenzen, bis sie sich treffen.
Die Antwort liegt zwischen low = 0 und high = len(numbers). Ist die Zahl in der Mitte kleiner als limit, liegt die Antwort rechts davon; sonst kann es die Mitte selbst sein: high = middle.
Wenn low und high gleich sind, ist das die Antwort.
In einer aufsteigend sortierten Liste stehen erst alle Zahlen unter limit, dann alle ab limit. Schreib firstAtLeast(numbers, limit), die den ersten Index ab limit zurückgibt, und die Länge der Liste, wenn keine Zahl so groß ist: firstAtLeast([1, 3, 3, 5, 8], 3) ergibt 1. Mit Halbieren: Bleib bei zwei Grenzen, bis sie sich treffen.
Die Antwort liegt zwischen low = 0 und high = numbers.length. Ist die Zahl in der Mitte kleiner als limit, liegt die Antwort rechts davon; sonst kann es die Mitte selbst sein: high = middle.
Wenn low und high gleich sind, ist das die Antwort.
Schreib int_sqrt(n), die die größte ganze Zahl k zurückgibt, für die k · k höchstens n ist: int_sqrt(20) ergibt 4, denn 4 · 4 = 16 und 5 · 5 = 25. Für n bis eine Billion, durch Halbieren zwischen 0 und n, ohne Math.sqrt und Integer.sqrt.
Die Antwort liegt zwischen low = 0 und high = n. Ist middle * middle <= n, kann middle die Antwort sein oder eine größere: low = middle. Sonst ist sie kleiner: high = middle - 1.
Nimm die Mitte aufgerundet, (low + high + 1) / 2, sonst bleibt low = middle bei zwei Zahlen stehen.
Schreib int_sqrt(n), die die größte ganze Zahl k zurückgibt, für die k · k höchstens n ist: int_sqrt(20) ergibt 4, denn 4 · 4 = 16 und 5 · 5 = 25. Für n bis eine Billion, durch Halbieren zwischen 0 und n, ohne math.sqrt und math.isqrt.
Die Antwort liegt zwischen low = 0 und high = n. Ist middle * middle <= n, kann middle die Antwort sein oder eine größere: low = middle. Sonst ist sie kleiner: high = middle - 1.
Nimm die Mitte aufgerundet, (low + high + 1) // 2, sonst bleibt low = middle bei zwei Zahlen stehen.
Schreib intSqrt(n), die die größte ganze Zahl k zurückgibt, für die k · k höchstens n ist: intSqrt(20) ergibt 4, denn 4 · 4 = 16 und 5 · 5 = 25. Für n bis eine Billion, durch Halbieren zwischen 0 und n, ohne Math.sqrt.
Die Antwort liegt zwischen low = 0 und high = n. Ist middle * middle <= n, kann middle die Antwort sein oder eine größere: low = middle. Sonst ist sie kleiner: high = middle - 1.
Nimm die Mitte aufgerundet, Math.floor((low + high + 1) / 2), sonst bleibt low = middle bei zwei Zahlen stehen.
Schreib insert_sorted(numbers, value), die eine neue Liste zurückgibt, in der value an der richtigen Position der aufsteigend sortierten Liste numbers steht: insert_sorted([1, 4, 9], 5) ergibt [1, 4, 5, 9]. Ohne zu sortieren: Such die Position und setz die Zahl dort ein. So arbeitet Insertion Sort, Zahl für Zahl.
Zwei Schritte: Such den ersten Index, an dem eine Zahl nicht mehr kleiner als value ist (oder das Ende); dann setz die Liste aus den drei Teilen davor, value und danach zusammen.
numbers[0...i] ist alles vor dem Index i, numbers[i..] alles ab ihm.
Schreib insert_sorted(numbers, value), die eine neue Liste zurückgibt, in der value an der richtigen Position der aufsteigend sortierten Liste numbers steht: insert_sorted([1, 4, 9], 5) ergibt [1, 4, 5, 9]. Ohne zu sortieren: Such die Position und setz die Zahl dort ein. So arbeitet Insertion Sort, Zahl für Zahl.
Zwei Schritte: Such den ersten Index, an dem eine Zahl nicht mehr kleiner als value ist (oder das Ende); dann setz die Liste aus den drei Teilen davor, value und danach zusammen.
numbers[:i] ist alles vor dem Index i, numbers[i:] alles ab ihm.
Schreib insertSorted(numbers, value), die eine neue Liste zurückgibt, in der value an der richtigen Position der aufsteigend sortierten Liste numbers steht: insertSorted([1, 4, 9], 5) ergibt [1, 4, 5, 9]. Ohne zu sortieren: Such die Position und setz die Zahl dort ein. So arbeitet Insertion Sort, Zahl für Zahl.
Zwei Schritte: Such den ersten Index, an dem eine Zahl nicht mehr kleiner als value ist (oder das Ende); dann setz die Liste aus den drei Teilen davor, value und danach zusammen.
numbers.slice(0, i) ist alles vor dem Index i, numbers.slice(i) alles ab ihm.
Schreib is_permutation(a, b), die true zurückgibt, wenn b dieselben Zahlen wie a enthält, jede gleich oft, nur vielleicht in anderer Reihenfolge, und sonst false: is_permutation([3, 1, 2], [1, 2, 3]) ergibt true. Ohne zu sortieren: Zähl, wie in einer Strichliste.
Eine Strichliste aus den Dictionaries: für a hochzählen, für b herunterzählen. Was bleibt bei einer Permutation übrig?
Schreib is_permutation(a, b), die True zurückgibt, wenn b dieselben Zahlen wie a enthält, jede gleich oft, nur vielleicht in anderer Reihenfolge, und sonst False: is_permutation([3, 1, 2], [1, 2, 3]) ergibt True. Ohne zu sortieren: Zähl, wie in einer Strichliste.
Eine Strichliste aus den Dictionaries: für a hochzählen, für b herunterzählen. Was bleibt bei einer Permutation übrig?
Schreib isPermutation(a, b), die true zurückgibt, wenn b dieselben Zahlen wie a enthält, jede gleich oft, nur vielleicht in anderer Reihenfolge, und sonst false: isPermutation([3, 1, 2], [1, 2, 3]) ergibt true. Ohne zu sortieren: Zähl, wie in einer Strichliste.
Eine Strichliste aus den Dictionaries: für a hochzählen, für b herunterzählen. Was bleibt bei einer Permutation übrig?
Eine aufsteigend sortierte Liste verschiedener Zahlen wurde gedreht: Ein Stück vom Anfang ist ans Ende gewandert, aus [1, 2, 3, 4, 5, 6] wurde [4, 5, 6, 1, 2, 3]. Schreib rotation_point(numbers), die den Index der kleinsten Zahl zurückgibt, dort, wo es wieder anfängt: hier 3. Mit Halbieren: Ist die Zahl in der Mitte größer als die letzte, liegt der Anfang rechts von ihr.
Wie bei »Ab wo?«: zwei Grenzen, bis sie sich treffen. Vergleich die Mitte mit numbers[high].
Eine aufsteigend sortierte Liste verschiedener Zahlen wurde gedreht: Ein Stück vom Anfang ist ans Ende gewandert, aus [1, 2, 3, 4, 5, 6] wurde [4, 5, 6, 1, 2, 3]. Schreib rotation_point(numbers), die den Index der kleinsten Zahl zurückgibt, dort, wo es wieder anfängt: hier 3. Mit Halbieren: Ist die Zahl in der Mitte größer als die letzte, liegt der Anfang rechts von ihr.
Wie bei »Ab wo?«: zwei Grenzen, bis sie sich treffen. Vergleich die Mitte mit numbers[high].
Eine aufsteigend sortierte Liste verschiedener Zahlen wurde gedreht: Ein Stück vom Anfang ist ans Ende gewandert, aus [1, 2, 3, 4, 5, 6] wurde [4, 5, 6, 1, 2, 3]. Schreib rotationPoint(numbers), die den Index der kleinsten Zahl zurückgibt, dort, wo es wieder anfängt: hier 3. Mit Halbieren: Ist die Zahl in der Mitte größer als die letzte, liegt der Anfang rechts von ihr.
Wie bei »Ab wo?«: zwei Grenzen, bis sie sich treffen. Vergleich die Mitte mit numbers[high].
Die kleinste Zahl finden und eine Zahl in eine sortierte Liste einsetzen sind die Bausteine zweier Sortierverfahren: Selection Sort sucht immer wieder die kleinste der übrigen Zahlen, Insertion Sort setzt eine Zahl nach der anderen an ihre Stelle. Ganze Sortierverfahren schreibst, beobachtest und vergleichst du in der Sorting Sandbox.
Ein Extra für Schnelle: Die Seite ist ohne dieses Kapitel vollständig.
Zwei Katas, die nicht mitzählen. Bei der zweiten zählt auch, wie schnell dein Code ist.
Schreib deine binäre Suche so um, dass sie zählt, wie oft sie in eine Mitte schaut, bis sie die Zahl hat oder der Bereich leer ist: search_steps([2, 5, 8, 12, 16, 23], 12) ergibt 3. Probier sie dann an langen Listen aus: Wie viele Schritte braucht sie bei 1000 Zahlen, bei einer Million? Wie viele die lineare Suche?
Deine binäre Suche mit einem Zähler, der in jedem Durchlauf der Schleife um eins wächst.
Schreib deine binäre Suche so um, dass sie zählt, wie oft sie in eine Mitte schaut, bis sie die Zahl hat oder der Bereich leer ist: search_steps([2, 5, 8, 12, 16, 23], 12) ergibt 3. Probier sie dann an langen Listen aus: Wie viele Schritte braucht sie bei 1000 Zahlen, bei einer Million? Wie viele die lineare Suche?
Deine binäre Suche mit einem Zähler, der in jedem Durchlauf der Schleife um eins wächst.
Schreib deine binäre Suche so um, dass sie zählt, wie oft sie in eine Mitte schaut, bis sie die Zahl hat oder der Bereich leer ist: searchSteps([2, 5, 8, 12, 16, 23], 12) ergibt 3. Probier sie dann an langen Listen aus: Wie viele Schritte braucht sie bei 1000 Zahlen, bei einer Million? Wie viele die lineare Suche?
Deine binäre Suche mit einem Zähler, der in jedem Durchlauf der Schleife um eins wächst.
numbers ist aufsteigend sortiert und hat 100 000 verschiedene Zahlen; queries hat 100 000 Zahlen, nach denen gesucht wird. Schreib count_found(numbers, queries), die zählt, wie viele davon in numbers stehen, in weniger als fünf Sekunden. Mit der linearen Suche dauert es Stunden.
Für jede Zahl aus queries eine binäre Suche in numbers. Deine Funktion von vorhin darfst du hier hineinschreiben und aufrufen.
numbers ist aufsteigend sortiert und hat 100 000 verschiedene Zahlen; queries hat 100 000 Zahlen, nach denen gesucht wird. Schreib count_found(numbers, queries), die zählt, wie viele davon in numbers stehen, in weniger als fünf Sekunden. Mit der linearen Suche dauert es Stunden.
Für jede Zahl aus queries eine binäre Suche in numbers. Deine Funktion von vorhin darfst du hier hineinschreiben und aufrufen.
numbers ist aufsteigend sortiert und hat 100 000 verschiedene Zahlen; queries hat 100 000 Zahlen, nach denen gesucht wird. Schreib countFound(numbers, queries), die zählt, wie viele davon in numbers stehen, in weniger als fünf Sekunden. Mit der linearen Suche dauert es Stunden.
Für jede Zahl aus queries eine binäre Suche in numbers. Deine Funktion von vorhin darfst du hier hineinschreiben und aufrufen.