Find First and Last Position of Element in Sorted Array

Q: Quelle est la complexité temporelle de la recherche de la première et de la dernière position ?

Un temps de O(log n) et un espace de O(1) , avec deux recherches binaires. Aucune ne s’arrête lorsqu’elle trouve une correspondance, donc le coût ne dépend pas du nombre de copies de la cible : environ 14 étapes par recherche pour 10^4 valeurs.

Q: Qu’est-ce qu’une borne inférieure dans une recherche binaire ?

La borne inférieure d’une valeur est le premier indice dont l’élément est supérieur ou égal à cette valeur, ou la longueur de la liste s’il n’y en a aucun. C’est l’endroit où la valeur serait insérée pour conserver le tri de la liste. La borne supérieure est le premier indice dont l’élément est strictement supérieur.

Q: Une seule fonction de recherche binaire peut-elle trouver à la fois le premier et le dernier indice ?

Oui. Ajoutez un indicateur à la recherche : en cas de correspondance, enregistrez l’indice et continuez à chercher vers la gauche pour trouver la première occurrence, ou vers la droite pour trouver la dernière. Effectuer une recherche de borne inférieure sur target et sur target + 1 fonctionne aussi. Les deux s’exécutent en O(log n) .

MoyenRecherche binaire

+10

Vous recevez une liste d’entiers nums triée par ordre non décroissant, donc une valeur peut apparaître plusieurs fois, ainsi qu’un entier target. Renvoyez une liste de deux indices, comptés à partir de 0 : la première et la dernière position où target apparaît. Si target ne figure pas dans la liste, renvoyez [-1, -1]. Visez un temps d’exécution de O(log n).

Fonction

searchRange(nums: integer-array, target: integer) → integer-array

numsinteger-array: la liste triée d’entiers, qui peut contenir des valeurs répétées
targetinteger: la valeur à rechercher
Renvoieinteger-array: le premier et le dernier indice de target, ou [-1, -1] s’il est absent

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums est trié par ordre non décroissant.

Exemples

Entrée: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
Sortie: [1, 3]
Explication: Les trois copies de 5 se trouvent aux index 1, 2 et 3, donc la séquence commence à l’index 1 et se termine à l’index 3. L’index 0 contient 3 et l’index 4 contient 8, donc la séquence ne peut pas s’étendre davantage.

Entrée: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
Sortie: [-1, -1]
Explication: 7 se trouverait entre 5 à l’index 3 et 8 à l’index 4, et aucun des deux n’est 7. La liste ne contient aucune copie, donc la réponse est [-1, -1].

Pour aller plus loin

Si la même liste reçoit des milliers de requêtes pour différentes cibles, un seul parcours préalable peut-il rendre chaque requête plus rapide que O(log n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une recherche binaire classique s’arrête sur la copie de target qu’elle rencontre, et cette copie peut se trouver n’importe où dans la série. Cherche plutôt une borne inférieure : le premier indice dont la valeur est supérieure ou égale à un nombre donné. Les bornes inférieures de target et de target + 1 donnent les deux extrémités de la série en O(log n).

Parcourez toute la liste

Intuition

Parcourez la liste une fois. Le premier indice contenant target est le début et le dernier est la fin. Si target n’apparaît jamais, les deux restent à -1.

Cela fonctionne avec n’importe quelle liste, triée ou non, et c’est là son inconvénient : il lit les n valeurs. Une liste de 10^4 valeurs coûte 10 000 comparaisons, alors qu’environ 28 suffiraient.

Algorithme

Définissez first = last = -1.
Pour chaque indice i, si nums[i] est égal à target, définissez first = i lorsque first est encore -1, et définissez last = i.
Renvoyez [first, last].

def searchRange(nums, target):
    first = last = -1
    for i, value in enumerate(nums):
        if value == target:
            if first == -1:
                first = i  # the first match fixes the start
            last = i  # every later match moves the end
    return [first, last]

Trouvez une copie, puis développez

Intuition

Effectuez une recherche binaire pour trouver un index contenant target. La liste est triée, donc toutes les occurrences se trouvent dans une séquence ininterrompue autour de cet index : avancez vers la gauche et vers la droite tant que le voisin est encore target.

La recherche coûte O(log n) et le parcours prend une étape par occurrence, soit k au total. Lorsque la plupart des éléments de la liste sont égaux à target, par exemple 10^4 occurrences, le parcours lit chaque valeur et vous revenez à un parcours linéaire.

Algorithme

Effectuez une recherche binaire pour trouver un index found tel que nums[found] == target.
S’il n’y en a aucun, renvoyez [-1, -1].
Déplacez first vers la gauche à partir de found tant que la valeur précédente est égale à target.
Déplacez last vers la droite à partir de found tant que la valeur suivante est égale à target.
Renvoyez [first, last].

def searchRange(nums, target):
    # An ordinary binary search finds some copy of target, if there is one.
    lo, hi = 0, len(nums) - 1
    found = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            found = mid
            break
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    if found == -1:
        return [-1, -1]
    # The copies sit next to each other, so walk out to both ends of the run.
    first = last = found
    while first > 0 and nums[first - 1] == target:
        first -= 1
    while last < len(nums) - 1 and nums[last + 1] == target:
        last += 1
    return [first, last]

Deux recherches binaires de borne inférieure

Intuition

Posons une autre question : quel est le premier indice dont la valeur est supérieure ou égale à value ? Cet indice est la borne inférieure, ou n si aucune valeur ne convient. Gardez un intervalle semi-ouvert [lo, hi) qui le contient toujours. Si nums[mid] < value, alors mid et tous les indices qui le précèdent ont une valeur trop petite. Sinon, mid convient, mais un indice antérieur pourrait aussi convenir, donc mid reste dans l’intervalle et devient le nouveau hi. La boucle ne s’arrête jamais prématurément lorsqu’elle trouve une correspondance.

La borne inférieure de target est l’indice où sa séquence commence. Les valeurs sont des entiers, donc la première valeur supérieure à target se trouve à la borne inférieure de target + 1, et la séquence se termine à l’indice qui la précède. Dans le premier exemple, la borne inférieure de 5 est 1 et celle de 6 est 4, où se trouve 8 : la séquence est [1, 3]. Les deux recherches prennent environ 28 étapes pour 10^4 valeurs, quelle que soit la longueur de la séquence.

Algorithme

Écrivez lowerBound(value) : commencez avec lo = 0, hi = n ; tant que lo < hi, si nums[mid] < value, définissez lo = mid + 1, sinon définissez hi = mid ; renvoyez lo.
Définissez first = lowerBound(target).
Si first == n ou nums[first] != target, renvoyez [-1, -1].
Définissez last = lowerBound(target + 1) - 1 et renvoyez [first, last].

def lowerBound(nums, value):
    # The first index whose number is at least value, or len(nums) if none is.
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < value:
            lo = mid + 1  # nums[mid] and everything before it is too small
        else:
            hi = mid  # nums[mid] qualifies, but an earlier index might too
    return lo


def searchRange(nums, target):
    first = lowerBound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    # The run of target ends right before the first number above target.
    last = lowerBound(nums, target + 1) - 1
    return [first, last]

Pièges et cas limites

Retourner dès que nums[mid] == target. Cet indice peut se trouver n’importe où dans la série : dans [3, 5, 5, 5, 8], le premier milieu est à l’indice 2, qui n’est à aucune des deux extrémités.
Écrire hi = mid - 1 dans la recherche de la borne inférieure lorsque nums[mid] ≥ value. Cela écarte mid, qui peut être la réponse.
Lire nums[first] sans vérifier first < n. Lorsque target est supérieur à toutes les valeurs, comme 13 dans les exemples, la borne inférieure est n, soit un indice après la fin.
Oublier le décalage en Lua et en R. Leurs listes commencent à 1 : il faut donc soustraire 1 aux deux positions.

Questions fréquentes3

Quelle est la complexité temporelle de la recherche de la première et de la dernière position ?

Un temps de O(log n) et un espace de O(1), avec deux recherches binaires. Aucune ne s’arrête lorsqu’elle trouve une correspondance, donc le coût ne dépend pas du nombre de copies de la cible : environ 14 étapes par recherche pour 10^4 valeurs.

Qu’est-ce qu’une borne inférieure dans une recherche binaire ?

La borne inférieure d’une valeur est le premier indice dont l’élément est supérieur ou égal à cette valeur, ou la longueur de la liste s’il n’y en a aucun. C’est l’endroit où la valeur serait insérée pour conserver le tri de la liste. La borne supérieure est le premier indice dont l’élément est strictement supérieur.

Une seule fonction de recherche binaire peut-elle trouver à la fois le premier et le dernier indice ?

Oui. Ajoutez un indicateur à la recherche : en cas de correspondance, enregistrez l’indice et continuez à chercher vers la gauche pour trouver la première occurrence, ou vers la droite pour trouver la dernière. Effectuer une recherche de borne inférieure sur target et sur target + 1 fonctionne aussi. Les deux s’exécutent en O(log n).

def searchRange(nums, target):
    # Écrivez le code ici

Test #1

Test #2

Arguments

nums = [3, 5, 5, 5, 8, 9, 9, 12]
target = 5

Résultat attendu

[1, 3]

Find First and Last Position of Element in Sorted Array

Fonction

Contraintes

Exemples

Indices

Solution

Parcourez toute la liste

Trouvez une copie, puis développez

Deux recherches binaires de borne inférieure

Pièges et cas limites

Questions fréquentes3

Problèmes similaires