Zwei Zeiger

Code in:JavaC#PythonJavaScript

Kurz gesagt: Zwei Zeiger, die an beiden Enden eines sortierten Arrays beginnen und sich aufeinander zubewegen, finden ein Paar mit gegebener Summe in O(n) statt O(n²).

Problem

Die Geschenkkarte und jedes Paar

Ein Kunde hat eine Geschenkkarte und will sie auf den Cent ausgeben: zwei Produkte, die zusammen genau so viel kosten wie die Karte. Die Seite sucht sie mit zwei verschachtelten Schleifen und prüft jedes Paar:

static long checks = 0;

static (int, int)? AllPairs(int[] prices, int card)
{
    for (int i = 0; i < prices.Length; i++)
    {
        for (int j = i + 1; j < prices.Length; j++)
        {
            checks++;
            if (prices[i] + prices[j] == card)
            {
                return (i, j);
            }
        }
    }
    return null;
}

Die Preisliste sind 1000 Produkte zu 2 €, 4 €, …, 2000 €, und die Karte hat 2001 €. Die Summe zweier gerader Preise ist nie ungerade, also gibt es kein Paar. Das ist der schlimmste Fall: Die Schleifen laufen bis zum Ende.

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
var pair = AllPairs(prices, card);
Console.WriteLine("Paar: " + (pair == null ? "keins" : "gefunden"));
Console.WriteLine("Prüfungen: " + checks);

Ausgabe

Paar: keins
Prüfungen: 499500

Fast eine halbe Million Prüfungen für 1000 Produkte. Es gibt n(n − 1) / 2 Paare, also ist das O(n²): Bei 100.000 Produkten werden es etwa 5 Milliarden.

Und die Preisliste ist nach Preis sortiert, doch die Schleifen nutzen das nicht.

Die Idee

Einer links, der andere rechts

Leg einen Finger auf den günstigsten Preis und einen anderen auf den teuersten. Die Finger sind Indizes: lo und hi. Addiere die beiden Preise:

• ist die Summe gleich der Karte, bist du fertig;
• ist sie zu klein, scheidet der günstige Preis aus: Selbst mit dem teuersten Preis im Spiel reicht es nicht. lo geht einen Preis nach rechts;
• ist sie zu groß, scheidet der teure Preis aus: Er ist selbst mit dem günstigsten zu viel. hi geht einen Preis nach links.

Jeder Schritt wirft einen Preis endgültig weg, und kein Paar, das die Antwort ist, geht verloren. Treffen sich lo und hi, sind die Preise aufgebraucht. Höchstens n − 1 Schritte: O(n).

Das heißt zwei Zeiger: zwei Indizes, die am Array entlanggehen, und jeder Vergleich sagt, welcher von ihnen sich bewegt. Hier gehen sie aufeinander zu. Die Idee kennst du aus der binären Suche, wo lo und hi den Bereich halten. Dort wirft jede Probe die Hälfte weg, hier einen Preis.

Die Bedingung ist dieselbe: Das Array muss sortiert sein. Nur dann stimmt „weiter rechts ist teurer“.

Sieh es dir an

lo und hi in der Preisliste

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Kein Paar für 50 €");
}

Ausgabe

19 € + 31 €

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

Schritt für Schritt, in Worten

1. Die Preisliste ist sortiert: 10 Preise. Die Geschenkkarte hat 50 €. lo steht auf dem günstigsten Preis, hi auf dem teuersten.
2. 3 € + 36 € = 39 € < 50 €: zu wenig. Selbst der teuerste Preis reicht für 3 € nicht, also scheidet 3 € aus: lo geht nach rechts.
3. 5 € + 36 € = 41 € < 50 €: zu wenig. Selbst der teuerste Preis reicht für 5 € nicht, also scheidet 5 € aus: lo geht nach rechts.
4. 8 € + 36 € = 44 € < 50 €: zu wenig. Selbst der teuerste Preis reicht für 8 € nicht, also scheidet 8 € aus: lo geht nach rechts.
5. 12 € + 36 € = 48 € < 50 €: zu wenig. Selbst der teuerste Preis reicht für 12 € nicht, also scheidet 12 € aus: lo geht nach rechts.
6. 15 € + 36 € = 51 € > 50 €: zu viel. 36 € ist selbst mit dem günstigsten Preis zu viel, also scheidet 36 € aus: hi geht nach links.
7. 15 € + 31 € = 46 € < 50 €: zu wenig. Selbst der teuerste Preis reicht für 15 € nicht, also scheidet 15 € aus: lo geht nach rechts.
8. 19 € + 31 € = 50 €: genau die Karte. findPair gibt die Indizes 5 und 8 zurück.
9. 7 Summen statt 45 Paare. Jeder Schritt wirft einen Preis endgültig weg, also sind es höchstens n − 1 Schritte.

Die Funktion gibt ein Tupel (int, int)? zurück: die zwei Indizes und null, wenn es kein Paar gibt. pair is (int lo, int hi) prüft, dass es einen Wert gibt, und zerlegt ihn in seine zwei Teile.

Genauer, für Neugierige

Warum kein Paar verloren geht. Sagen wir, die Antwort ist das Indexpaar i und j, i < j. Solange lo ≤ i und hi ≥ j, können die Zeiger die Antwort nicht überspringen:

• ist lo < i, ist die Summe aus lo und hi höchstens die Summe aus i und hi. Ist sie zu klein, geht lo zu Recht nach rechts, ohne i zu überschreiten;
• ist hi > j, geht auf dieselbe Weise hi zu Recht nach links, ohne j zu überschreiten.

Erreicht lo das i und hi das j, ist die Summe genau die Karte. Gibt es mehrere Paare, finden die Zeiger das äußerste: das mit dem günstigsten Preis.

Probier es aus

Sag voraus, welches Paar

Die Karte hat 43 €. Die Preisliste hat zwei Paare mit dieser Summe: 12 € + 31 € und 19 € + 24 €. Was gibt das Programm aus?

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 43);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Kein Paar für 43 €");
}

Antwort

19 € + 24 €

Kein Paar für 43 €

12 € + 31 €

Prüfen

Probier es aus

Ergänze

Die Summe ist kleiner als die Karte. Welcher Zeiger bewegt sich, und in welche Richtung?

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            ;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

Prüfen

Probier es aus

Finde den Fehler

Die Karte hat 50 €, und 19 € + 31 € stehen in der Preisliste. Die Funktion sagt, es gibt kein Paar:

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Kein Paar für 50 €");
}

Ausgabe

Kein Paar für 50 €

Wähle die Zeile mit dem Fehler.

1static (int, int)? FindPair(int[] prices, int card)2{3 int lo = 0;4 int hi = prices.Length - 1;5 while (lo < hi)6 {7 int sum = prices[lo] + prices[hi];8 if (sum == card)9 {10 return (lo, hi);11 }12 else if (sum < card)13 {14 hi--;15 }16 else17 {18 hi--;19 }20 }21 return null;22}

Prüfen

Sieh es dir an

Wie viele Schritte

Dieselbe Preisliste mit 1000 Produkten und die Karte über 2001 €, und die Funktion zählt die Schritte ihrer Schleife:

static long steps = 0;

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        steps++;
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
var pair = FindPair(prices, card);
Console.WriteLine("Paar: " + (pair == null ? "keins" : "gefunden"));
Console.WriteLine("Schritte: " + steps);

Ausgabe

Paar: keins
Schritte: 999

999 Schritte statt 499.500 Prüfungen. Die zwei Funktionen geben dieselbe Antwort, und bei 100.000 Produkten ist der Unterschied 99.999 Schritte gegen etwa 5 Milliarden.

Lass sie im Browser laufen. Die dritte Kurve gilt für eine unsortierte Preisliste: erst Mergesort, dann die zwei Zeiger.

• Jedes Paar O(n²)
• Zwei Zeiger (sortierte Liste) O(n)
• Sortieren, dann zwei Zeiger O(n log n)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Jedes Paar	45	499.500	49.995.000	≈ 4.999.500.000
Zwei Zeiger (sortierte Liste)	9	999	9.999	99.999
Sortieren, dann zwei Zeiger	31	9.692	130.424	1.636.539

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

Über 10.000 lassen wir nicht jedes Paar laufen: Diese Werte sind mit ≈ gekennzeichnet. Das Sortieren kostet mehr als die Zeiger selbst, aber seine Kurve ist O(n log n) und liegt immer noch weit unter O(n²).

Die Idee

Ist die Liste sortiert

Zwei Zeiger brauchen ein sortiertes Array. Ist es das nicht:

• Sortiere es zuerst. Sortieren ist O(n log n), die Zeiger O(n), insgesamt O(n log n). Bei 100.000 Preisen sind das etwa 1,6 Millionen Operationen gegen etwa 5 Milliarden. Sortieren gewinnt fast immer.
• Wenn du oft suchst in derselben Liste (jeder Kunde mit einer anderen Karte), sortierst du einmal, und jede Suche danach ist O(n).
• Die Indizes ändern sich. Nach dem Sortieren ist prices[5] nicht mehr das fünfte Produkt des Katalogs. Brauchst du die Produkte, sortiere Paare (Preis, Produkt) oder Objekte nach Preis.

int[] prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
Array.Sort(prices);
Console.WriteLine("[" + string.Join(", ", prices) + "]");
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Kein Paar für 50 €");
}

Ausgabe

[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
19 € + 31 €

Es gibt auch einen Weg ohne Sortieren: Du gehst einmal über die Preise und behältst die gesehenen in einem Set. Für jeden Preis fragst du, ob card − price schon gesehen wurde. Das ist im Durchschnitt O(n), mit einer Hashtabelle und n zusätzlichem Speicher. Zwei Zeiger brauchen keinen zusätzlichen Speicher, aber ein sortiertes Array.

Sieh es dir an

Dieselbe Idee: Mischen und Duplikate

Die zwei Zeiger gehen nicht immer aufeinander zu. Manchmal gehen sie in dieselbe Richtung.

Zwei sortierte Listen mischen. Die Bestellungen von der Website und vom Telefon werden von einem Zähler nummeriert, aber getrennt geführt, jede Liste sortiert. Der Tagesbericht will eine sortierte Liste. i geht an der ersten entlang, j an der zweiten, und jedes Mal kommt die kleinere Nummer ins Ergebnis. Das ist das Mischen aus dem Mergesort:

static int[] Merge(int[] a, int[] b)
{
    int[] result = new int[a.Length + b.Length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < a.Length && j < b.Length)
    {
        if (a[i] <= b[j])
        {
            result[k++] = a[i++];
        }
        else
        {
            result[k++] = b[j++];
        }
    }
    while (i < a.Length)
    {
        result[k++] = a[i++];
    }
    while (j < b.Length)
    {
        result[k++] = b[j++];
    }
    return result;
}

int[] web = [1003, 1007, 1012, 1020];
int[] phone = [1001, 1009, 1010, 1031, 1044];
Console.WriteLine("[" + string.Join(", ", Merge(web, phone)) + "]");

Ausgabe

[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Duplikate an Ort und Stelle. Die Preise aus einem Import sind sortiert, aber mit Duplikaten, und der Filter muss jeden Preis einmal zeigen. read liest jeden Preis, und write ist der Platz für den nächsten neuen. Alles vor write ist fertig und frei von Duplikaten:

static int Unique(int[] prices)
{
    if (prices.Length == 0)
    {
        return 0;
    }
    int write = 1;
    for (int read = 1; read < prices.Length; read++)
    {
        if (prices[read] != prices[write - 1])
        {
            prices[write] = prices[read];
            write++;
        }
    }
    return write;
}

int[] prices = [5, 5, 8, 12, 12, 12, 19, 24, 24];
int k = Unique(prices);
Console.WriteLine("Verschiedene Preise: " + k);
Console.WriteLine("[" + string.Join(", ", prices[..k]) + "]");

Ausgabe

Verschiedene Preise: 5
[5, 8, 12, 19, 24]

Ein Array in C# hat eine feste Länge: Die Funktion gibt zurück, wie viele verschiedene Preise es gibt, und das Programm zeigt nur diese (prices[..k]).

Beide sind O(n): Jeder Zeiger geht einmal über die Liste.

Sieh es dir an

Ein Spiegel-Gutscheincode

Die Aktion „Spiegelcode“ akzeptiert nur Gutscheincodes, die sich von beiden Enden gleich lesen. Die Zeiger beginnen an beiden Enden und vergleichen Zeichen für Zeichen, bis sie sich treffen:

static bool IsMirror(string code)
{
    int lo = 0;
    int hi = code.Length - 1;
    while (lo < hi)
    {
        if (code[lo] != code[hi])
        {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

Console.WriteLine(IsMirror("AB7CC7BA"));
Console.WriteLine(IsMirror("AB7CD7BA"));

Ausgabe

True
False

Genauer, für Neugierige

Dieselbe Prüfung lässt sich in einer Zeile schreiben, indem man den Code mit einer umgedrehten Kopie vergleicht:

string code = "AB7CC7BA";
Console.WriteLine(code == new string(code.Reverse().ToArray()));

Ausgabe

True

code.Reverse() ist LINQ: Es geht die Zeichen von hinten nach vorn durch, und new string(… .ToArray()) sammelt sie in einem neuen String.

Die Antwort ist dieselbe, und es ist immer noch O(n). Der Unterschied: Die Kopie sind n Zeichen mehr Speicher und wird immer ganz gemacht, während die Zeiger beim ersten Unterschied anhalten. Bei einem Gutscheincode mit 8 Zeichen spielt das keine Rolle. Bei der Prüfung von Millionen Zeilen in einem Log schon.

Dieselben Zeiger drehen ein Array an Ort und Stelle um: lo und hi vertauschen, nach innen bewegen.

Übung

Am nächsten an der Karte

Löse die Aufgabe in deinem Editor.

Am nächsten an der Karte. Es gibt nicht immer ein genaues Paar. Dann bietet der Shop die zwei Produkte an, die zusammen der Karte am nächsten kommen, ohne sie zu überschreiten. Die Preisliste ist 3 €, 5 €, 8 €, 12 €, 15 €, 19 €, 24 €, 27 €, 31 € und 36 €, und die Karte hat 45 €. Mit zwei Zeigern: Liegt die Summe innerhalb der Karte, merke sie dir, wenn sie besser ist als die bisher beste, und bewege lo. Sonst bewege hi.

Ausgabe

Am nächsten an 45 €: 8 € + 36 € = 44 €

Weitere Aufgaben

• Ein Spiegelcode mit Bindestrichen. Die Gutscheincodes werden mit Bindestrichen gedruckt: AB7-CC-7BA. Überspringe die Bindestriche: Jeder Zeiger springt vor dem Vergleich über sie hinweg.
• Zwei pro Fahrt. Die Pakete sind nach Gewicht sortiert, und eine Kurierfahrt trägt höchstens zwei Pakete mit zusammen bis zu 30 kg. Wie viele Fahrten braucht man mindestens? Leg das leichteste mit dem schwersten zusammen, wenn sie passen, sonst fährt das schwerste allein.
• Gemeinsame Produkte. Zwei sortierte Listen von Produktnummern: aus dem Lager und aus der Bestellung. Finde mit zwei Zeigern in dieselbe Richtung, welche Nummern in beiden stehen.

Test

Teste dich

1. Die Preisliste ist sortiert. lo steht auf 8 €, hi auf 36 €, die Karte hat 50 €. Die Summe ist 44 €. Was tust du?

lo geht nach rechts: 8 € reichen auch mit dem teuersten Preis nichtDu gehst zurück zum Anfanghi geht nach links

2. Die Preisliste hat 100.000 Produkte, und es gibt kein Paar für die Karte. Wie viele Summen berechnen die zwei Zeiger?

99.999Etwa 17, so viele wie die binäre SucheEtwa 5 Milliarden

3. Die Preisliste ist nicht sortiert. Was ist von den dreien am schnellsten?

Sortieren (O(n log n)) und die zwei Zeiger laufen lassen (O(n))Die zwei Zeiger direkt auf der unsortierten Liste laufen lassenJedes Paar (O(n²)), weil das Sortieren zu viel kostet

4. Du entfernst die Duplikate aus der sortierten Liste an Ort und Stelle, mit read und write. Was stimmt?

read geht über jedes Element, und write zeigt, wo der fertige Teil endetDu brauchst eine neue Liste derselben Längeread und write gehen von beiden Enden aufeinander zu

5. Warum ist die Prüfung eines Spiegel-Gutscheincodes mit zwei Zeigern besser als der Vergleich mit einer umgedrehten Kopie?

Sie macht keine Kopie und hält beim ersten Unterschied anDie umgedrehte Kopie gibt eine falsche AntwortSie ist O(log n)

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Binäre Suche · Mergesort und „Teile und herrsche“ · Stabiles Sortieren und die eingebaute Sortierung · Hashtabelle
• Geht weiter in: Gleitendes Fenster · Eine Hashtabelle als Zähler
• Aufgaben zum Thema: Techniken zum Lösen von Aufgaben