Tester les bornes de recherche dichotomique iOS sur un Mac cloud

Après avoir développé la logique d’une liste sous Windows, on peut valider le code Swift sur un Mac cloud. Le point le plus facile à négliger n’est pas la capacité à retrouver un élément, mais la position à laquelle insérer les valeurs en double. Un fil de discussion, des graduations par segments ou un index d’enregistrements triés peuvent tous reposer sur une recherche dichotomique. Un décalage d’une seule position peut passer inaperçu sur les exemples courants, puis faire perdre des enregistrements dans les cas limites. Nous allons définir un contrat exécutable dans un script autonome, sans lancer de simulateur ni utiliser de données réseau.

Définir les deux bornes d’insertion

On suppose que l’entrée est un tableau d’entiers trié par ordre croissant. La borne inférieure renvoie la première position dont la valeur est supérieure ou égale à la cible ; la borne supérieure renvoie la première position dont la valeur est strictement supérieure à la cible. Leur différence donne le nombre d’occurrences de la cible.

Par exemple, dans le tableau [1, 2, 2, 4], la recherche de 2 donne une borne inférieure de 1 et une borne supérieure de 3. Pour 5, les deux fonctions renvoient 4 : il s’agit d’une position d’insertion en fin de tableau, pas d’un échec de recherche.

La position renvoyée peut être égale à la longueur du tableau, mais cet indice ne permet pas de lire un élément. Vérifiez d’abord les limites, puis accédez à l’élément. Le dernier élément ne doit pas servir de substitut à la position d’insertion en fin de tableau.

Nous n’utilisons pas de sentinelle -1 et les fonctions ne trient pas automatiquement leurs entrées. Un tri automatique masquerait les données désordonnées transmises par l’appelant et pourrait aussi altérer l’ordre relatif initial des enregistrements.

Implémenter la recherche avec un intervalle semi-ouvert

Une fois connecté au Mac cloud, créez BoundsCheck.swift dans votre répertoire de travail. Exécutez d’abord xcrun --find swift pour vérifier que la chaîne d’outils est disponible, puis ajoutez l’implémentation suivante. L’intervalle de recherche reste toujours [lo, hi), avec une borne supérieure initiale égale à la longueur du tableau.

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
}

Seule la condition de comparaison distingue les deux fonctions, mais cette différence détermine de quel côté se placent les doublons. Le calcul du milieu, lo + (hi - lo) / 2, évite d’additionner directement les deux bornes. L’intervalle doit rétrécir à chaque itération : ne remplacez pas la borne gauche par mid, sinon la boucle risque de ne jamais se terminer avec deux éléments.

Un tableau vide ne nécessite aucun traitement particulier : la boucle ne s’exécute pas et la fonction renvoie directement zéro. N’introduisez pas count - 1 pour gérer ce cas, au risque de retrouver des indices négatifs et les conditions d’arrêt propres aux intervalles fermés.

Vérifier exhaustivement les petits tableaux avec une référence linéaire

L’implémentation de référence doit être simple, et non constituer une seconde recherche dichotomique. Ajoutez le code suivant au même fichier. Il énumère tous les tableaux non décroissants de longueur zéro à six dont les éléments vont de zéro à trois, puis teste des cibles à l’intérieur et à l’extérieur de cette plage.

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)

Exécutez xcrun swift BoundsCheck.swift. Un code de sortie nul indique que toutes les assertions ont réussi ; en cas d’échec, le processus se termine avec un code non nul. Le script n’utilise pas les appels ordinaires à assert, qui peuvent être supprimés lors d’une compilation optimisée. N’utilisez pas non plus d’options de compilation désactivant les contrôles de sécurité.

Intégrer les résultats à l’interface métier

Pour vérifier la présence d’un élément, calculez d’abord la borne inférieure. La recherche n’est positive que si cette position est inférieure à la longueur du tableau et si la valeur correspondante est égale à la cible. Pour récupérer toutes les occurrences d’une valeur, utilisez la tranche lower..<upper ; si la cible est absente, cette tranche est naturellement vide.

Garder un ordre de tri et une comparaison cohérents

Si le tableau contient des enregistrements triés par horodatage, la recherche doit utiliser la même sémantique d’horodatage. Trier par date croissante, puis comparer les chaînes d’affichage pendant la recherche, ne peut pas fonctionner correctement, même si l’algorithme lui-même est juste.

Pour conserver l’ordre d’arrivée des enregistrements ayant le même horodatage, on peut les insérer à la borne supérieure. Si des priorités métier interviennent également, définissez d’abord une clé de tri complète au lieu de compter sur la position d’insertion pour remplacer les règles de tri. Les conditions de comparaison présentées ici ne sont pas directement réutilisables avec un tableau trié par ordre décroissant.

Le tableau doit également rester inchangé pendant la recherche. Si une position est obtenue de manière asynchrone, puis que le tableau est modifié, cette position peut ne plus être valide. Effectuez la recherche et l’insertion dans le même domaine d’isolation, ou travaillez sur un même instantané immuable.

Constituer une liste de tests de régression à partir des échecs

Lors de l’intégration aux tests du projet, conservez trois niveaux de vérification : des cas métier fixes, l’énumération exhaustive de petits tableaux et le contrat de tri des enregistrements réels. Ne vous contentez pas de vérifier que la valeur renvoyée se trouve dans les limites autorisées : une position valide peut malgré tout être décalée d’un élément.

• Couvrir le tableau vide, le tableau à un seul élément, les tableaux dont tous les éléments sont identiques et les cibles situées au-delà des deux extrémités.
• Vérifier que toutes les valeurs à gauche de la borne inférieure sont strictement inférieures à la cible et que toutes celles à partir de la borne supérieure lui sont strictement supérieures.
• Vérifier que la longueur de l’intervalle des doublons correspond au nombre d’occurrences obtenu par un parcours linéaire.
• Enregistrer chaque tableau en échec, sa cible et les positions attendues comme cas de test fixes.
• Relancer les tests avec la chaîne d’outils et la configuration de compilation réellement utilisées.

L’énumération exhaustive de petits tableaux ne prouve pas la correction pour toutes les entrées entières possibles, mais elle couvre systématiquement les doublons et les chemins de réduction de l’intervalle. Même si l’implémentation évolue ensuite vers un comparateur générique, conservez la référence linéaire et les assertions de partitionnement afin que les optimisations reposent sur un contrat d’interface inchangé.

Questions fréquentes