iOS-Binärsuche auf einem Cloud-Mac prüfen

Wenn die Listenlogik unter Windows fertiggestellt ist und der Swift-Code anschließend auf einem Cloud-Mac geprüft wird, gerät eine Frage besonders leicht aus dem Blick: nicht, ob sich ein Element finden lässt, sondern an welcher Position doppelte Werte eingefügt werden müssen. Chat-Zeitachsen, segmentierte Skalen und sortierte Datensatzindizes können auf einer Binärsuche beruhen. Schon ein Versatz um eine Position kann bei üblichen Beispielen unbemerkt bleiben, bei Grenzfällen aber zum Verlust von Datensätzen führen. Im Folgenden legen wir mit einem eigenständigen Skript einen ausführbaren Vertrag fest – ohne Simulator und ohne Daten aus dem Netzwerk.

Zuerst die beiden Einfügegrenzen definieren

Die Eingabe sei ein aufsteigend sortiertes Integer-Array. Die untere Grenze liefert die erste Position, deren Wert größer oder gleich dem Zielwert ist. Die obere Grenze liefert die erste Position, deren Wert strikt größer als der Zielwert ist. Die Differenz beider Positionen entspricht der Anzahl der Vorkommen des Zielwerts.

Bei der Suche nach 2 im Array [1, 2, 2, 4] ist die untere Grenze beispielsweise 1 und die obere Grenze 3. Für 5 liefern beide Funktionen 4: Das ist die Einfügeposition am Array-Ende und kein fehlgeschlagener Suchvorgang.

Die zurückgegebene Position darf der Array-Länge entsprechen. Als Index für einen Lesezugriff ist sie dann jedoch ungültig. Prüfen Sie zuerst die Grenzen und lesen Sie erst danach das Element. Das letzte Element ist kein Ersatz für die Einfügeposition am Array-Ende.

Wir verwenden weder einen Sentinelwert -1 noch lassen wir die Funktionen automatisch sortieren. Automatisches Sortieren würde verdecken, dass der Aufrufer unsortierte Daten übergeben hat. Außerdem könnte es die ursprüngliche Reihenfolge der Datensätze verändern.

Die Suche mit einem halboffenen Intervall implementieren

Melden Sie sich am Cloud-Mac an und erstellen Sie in Ihrem Arbeitsverzeichnis die Datei BoundsCheck.swift. Prüfen Sie zunächst mit xcrun --find swift, ob die Toolchain verfügbar ist, und fügen Sie dann die folgende Implementierung ein. Das Suchintervall ist stets [lo, hi); seine obere Grenze entspricht zu Beginn der Array-Länge.

func lowerBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

func upperBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

Die beiden Funktionen unterscheiden sich nur in der Vergleichsbedingung. Genau dieser Unterschied legt jedoch fest, auf welcher Seite die Duplikate liegen. Die Mitte wird als lo + (hi - lo) / 2 berechnet, um die Grenzen nicht direkt addieren zu müssen. Das Intervall muss in jedem Durchlauf kleiner werden. Setzen Sie die linke Grenze nicht auf mid, sonst kann die Schleife bei einer Eingabe mit zwei Elementen endlos laufen.

Ein leeres Array benötigt keinen Sonderfall: Die Schleife wird nicht ausgeführt, und die Funktion liefert direkt null. Führen Sie zur Behandlung leerer Arrays kein count - 1 ein. Damit würden negative Indizes und die Abbruchbedingungen geschlossener Intervalle wieder zum Thema.

Alle kleinen Arrays mit einer linearen Referenz prüfen

Die Referenzimplementierung sollte einfach sein und nicht aus einer zweiten Binärsuche bestehen. Hängen Sie den folgenden Code an dieselbe Datei an. Er erzeugt alle monoton nicht fallenden Arrays der Längen null bis sechs mit Elementwerten von null bis drei und prüft anschließend Zielwerte innerhalb und außerhalb dieses Wertebereichs.

func verify(_ values: [Int]) {
    for target in -1...4 {
        let lower = lowerBound(values, target)
        let upper = upperBound(values, target)
        let expectedLower =
            values.firstIndex(where: { $0 >= target }) ?? values.count
        let expectedUpper =
            values.firstIndex(where: { $0 > target }) ?? values.count

        precondition(lower == expectedLower)
        precondition(upper == expectedUpper)
        precondition(lower <= upper)
        precondition(values[..<lower].allSatisfy { $0 < target })
        precondition(values[lower...].allSatisfy { $0 >= target })
        precondition(values[..<upper].allSatisfy { $0 <= target })
        precondition(values[upper...].allSatisfy { $0 > target })
    }
}

func enumerate(_ prefix: [Int], remaining: Int, minimum: Int) {
    if remaining == 0 {
        verify(prefix)
        return
    }
    for value in minimum...3 {
        enumerate(prefix + [value],
                  remaining: remaining - 1,
                  minimum: value)
    }
}

for length in 0...6 {
    enumerate([], remaining: length, minimum: 0)
}
verify([Int.min, 0, Int.max])
precondition(lowerBound([Int.min, 0, Int.max], Int.min) == 0)
precondition(upperBound([Int.min, 0, Int.max], Int.max) == 3)

Führen Sie xcrun swift BoundsCheck.swift aus. Der Exitcode null bedeutet, dass alle Zusicherungen erfüllt sind. Schlägt eine Prüfung fehl, endet der Prozess mit einem Exitcode ungleich null. Das Skript verwendet keine gewöhnlichen assert-Aufrufe, die bei optimierten Builds entfernt werden können. Verwenden Sie auch keine Compileroptionen, die Sicherheitsprüfungen abschalten.

Die Ergebnisse in die Fachschnittstelle einbinden

Um festzustellen, ob ein Element vorhanden ist, ermitteln Sie zunächst die untere Grenze. Ein Treffer liegt nur dann vor, wenn die Position kleiner als die Array-Länge ist und der Wert an dieser Position dem Zielwert entspricht. Alle Vorkommen eines Werts erhalten Sie mit dem Slice lower..<upper. Ist der Zielwert nicht vorhanden, ist dieser Slice automatisch leer.

Sortierung und Vergleich konsistent halten

Enthält das Array Datensätze, die nach Zeitstempel sortiert sind, muss auch die Suche dieselbe Zeitstempelsemantik verwenden. Wer aufsteigend nach Zeit sortiert, bei der Suche aber die angezeigten Zeichenketten vergleicht, erhält auch mit einem korrekten Algorithmus kein verlässliches Ergebnis.

Soll bei gleichen Zeitstempeln die Eingangsreihenfolge erhalten bleiben, bietet sich das Einfügen an der oberen Grenze an. Gibt es zusätzlich fachliche Prioritäten, definieren Sie zuerst einen vollständigen Sortierschlüssel, statt die Einfügeposition als Ersatz für eine Sortierregel zu verwenden. Für absteigend sortierte Arrays lassen sich die hier verwendeten Vergleichsbedingungen nicht unverändert übernehmen.

Während der Suche muss das Array außerdem unverändert bleiben. Wird eine Position asynchron ermittelt und das Array danach verändert, kann die alte Position bereits ungültig sein. Führen Sie Suche und Einfügen innerhalb derselben Isolationsdomäne aus oder arbeiten Sie auf demselben unveränderlichen Snapshot.

Aus Fehlerfällen eine Regressionscheckliste erstellen

Behalten Sie bei der Übernahme in die Projekttests drei Prüfebenen bei: feste fachliche Testfälle, die vollständige Aufzählung kleiner Arrays und den Sortiervertrag für reale Datensätze. Prüfen Sie nicht nur, ob der Rückgabewert im gültigen Bereich liegt. Auch eine gültige Position kann um ein Element verschoben sein.

• Leere Arrays, Arrays mit einem Element, ausschließlich gleiche Werte und Zielwerte außerhalb beider Enden abdecken.
• Prüfen, dass alle Werte links von der unteren Grenze kleiner als der Zielwert und alle Werte ab der oberen Grenze größer als der Zielwert sind.
• Prüfen, dass die Länge des Duplikatintervalls der linear ermittelten Anzahl der Vorkommen entspricht.
• Das fehlerauslösende Array, den Zielwert und die erwarteten Positionen als feste Testfälle speichern.
• Die Tests mit der tatsächlich eingesetzten Toolchain und Build-Konfiguration erneut ausführen.

Die vollständige Prüfung kleiner Arrays ist kein Korrektheitsbeweis für alle möglichen Integer-Eingaben. Sie deckt aber Duplikate und die verschiedenen Wege der Intervallverkleinerung systematisch ab. Behalten Sie die lineare Referenz und die Zusicherungen zur Partitionierung auch dann bei, wenn Sie später auf einen generischen Vergleicher umstellen. So beruhen Optimierungen weiterhin auf einem unveränderten Schnittstellenvertrag.

Häufig gestellte Fragen