Search in Rotated Sorted Array

Q: Quelle est la complexité temporelle de la recherche dans un tableau trié pivoté ?

Un temps O(log n) et un espace supplémentaire O(1) . À chaque étape, on conserve une moitié de l’intervalle, donc 5000 éléments nécessitent au maximum 13 étapes. Trouver d’abord le point de rotation est également en O(log n) , avec environ deux fois plus d’étapes.

Q: ’algorithme fonctionne-t-il lorsque le tableau contient des doublons ?

Pas tel que c’est écrit. Lorsque nums[lo] , nums[mid] et nums[hi] sont égaux, il est impossible de prouver que l’une ou l’autre moitié est triée. La solution habituelle consiste alors à avancer lo d’une position, ce qui préserve la correction de la réponse, mais donne un cas le pire de O(n) .

Q: Devez-vous d’abord trouver le point de rotation ou effectuer la recherche en un seul passage ?

Les deux s’exécutent en O(log n) . Trouver le minimum revient d’abord à diviser le problème en deux recherches binaires simples. La recherche en un seul passage fait le travail en une seule boucle avec moins d’étapes, et c’est la version à laquelle la plupart des intervieweurs s’attendent.

MoyenRecherche binaire

+10

Une liste d’entiers distincts a été triée par ordre croissant, puis pivotée : un certain nombre d’éléments, éventuellement zéro, ont été pris au début et déplacés à la fin dans le même ordre. Par exemple, [2, 5, 8, 11, 15, 19, 23] pivotée de 4 devient [15, 19, 23, 2, 5, 8, 11]. On vous donne la liste pivotée nums et un entier target. Renvoyez l’indice de target dans nums, en commençant à compter à partir de 0, ou -1 s’il n’y figure pas, en temps O(log n).

Fonction

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

numsinteger-array: la liste triée par rotation d’entiers distincts
targetinteger: la valeur à rechercher
Renvoieinteger: l’indice de target dans nums, ou -1 s’il est absent

Contraintes

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
Toutes les valeurs de nums sont distinctes.
nums est une liste croissante décalée de k positions, avec 0 ≤ k < nums.length ; k = 0 la laisse inchangée.

Exemples

Entrée: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Sortie: 4
Explication: Le premier élément du milieu, à l’index 3, contient 2 ; la moitié droite [2, 5, 8, 11] est triée et contient 5. L’élément suivant du milieu, à l’index 5, contient 8 ; la partie gauche triée [5, 8] contient 5, ce qui mène à l’index 4.

Entrée: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Sortie: -1
Explication: 65 se trouverait entre 60 et 70, et aucun élément ne le contient. Le premier élément central, 70, place 65 dans la partie gauche triée [40, 50, 60, 70], et l’intervalle s’y réduit jusqu’à être vide.

Entrée: nums = [8, 13, 21, 1, 3, 5]target = 13
Sortie: 1
Explication: Le premier élément du milieu, à l’indice 2, contient 21. La partie gauche [8, 13, 21] est triée et 13 se trouve entre 8 et 21, donc la partie droite est écartée. La recherche trouve alors 13 à l’indice 1.

Pour aller plus loin

Si nums peut contenir des doublons, aucun algorithme ne peut garantir O(log n). Peux-tu le prouver avec une liste pivotée de 1 qui dissimule un seul 0 ?

Indices

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

0 sur 3 ouverts

Solution

Une liste triée et pivotée se compose de deux suites triées : [15, 19, 23] puis [2, 5, 8, 11]. Comparer target à la valeur médiane ne vous indique plus dans quelle moitié il se trouve. Mais, où que vous coupiez la liste, au moins une moitié est triée, et une comparaison vous indique si target peut se trouver dans cette moitié.

Parcourir chaque élément

Intuition

Vérifie chaque indice et renvoie le premier dont la valeur est égale à target, ou -1 après la boucle. Il lit chaque élément, donc il est correct pour toute liste. Il ignore les deux séquences triées : 5000 éléments nécessitent jusqu’à 5000 comparaisons, alors qu’une recherche binaire en nécessite 13.

Algorithme

Pour chaque indice i de 0 à n-1, compare nums[i] à target.
S’ils sont égaux, retourne i.
Après la boucle, retourne -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Trouvez le point de rotation, puis effectuez une recherche binaire

Intuition

La deuxième séquence commence à la plus petite valeur ; appelons son indice k. nums[k..n-1] et nums[0..k-1] sont toutes deux triées, et chaque valeur de la première séquence est supérieure à chaque valeur de la deuxième. Une fois que tu connais k, comparer target à nums[k] et nums[n-1] permet de choisir la séquence, puis une recherche binaire classique termine le travail.

Pour trouver k, compare la valeur du milieu à nums[hi]. Si nums[mid] > nums[hi], les valeurs diminuent quelque part après mid, donc le minimum se trouve à sa droite. Sinon, nums[mid..hi] augmente sans diminution, donc le minimum se trouve à mid ou avant. Dans le premier exemple, les valeurs du milieu sont 2, 19 et 23, ce qui donne k = 3, et 5 se trouve entre nums[3] = 2 et nums[6] = 11. Deux recherches binaires coûtent environ 2 log2 n étapes.

Algorithme

Définis lo = 0 et hi = n-1. Tant que lo < hi, calcule mid ; si nums[mid] > nums[hi], définis lo = mid + 1, sinon définis hi = mid.
L’index final k contient la plus petite valeur.
Si nums[k] ≤ target ≤ nums[n-1], effectue une recherche binaire sur les index de k à n-1 ; sinon, recherche de 0 à k-1.
Renvoie l’index trouvé, ou -1 si l’intervalle est vide.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Une recherche binaire sur la moitié triée

Intuition

Respecte la promesse de la recherche binaire : si target se trouve dans la liste, son indice est compris entre lo et hi. Les valeurs ne diminuent qu’une seule fois dans toute la liste, donc au plus une des deux moitiés autour de mid contient cette diminution, et l’autre est triée. Si nums[lo] ≤ nums[mid], la moitié gauche est triée ; sinon, c’est la moitié droite.

Pour la moitié triée, un test de plage sur ses deux extrémités indique si target peut se trouver à l’intérieur, par exemple nums[lo] ≤ target < nums[mid] dans la moitié gauche. Si c’est possible, cherche dans cette moitié ; sinon, target ne peut se trouver que dans l’autre moitié. À chaque étape, la plage est divisée par deux : au maximum 13 étapes pour 5000 éléments.

Algorithme

Définissez lo = 0 et hi = n-1.
Tant que lo ≤ hi, calculez mid et renvoyez-le si nums[mid] est égal à target.
Si nums[lo] ≤ nums[mid], la moitié gauche est triée : définissez hi = mid - 1 lorsque nums[lo] ≤ target < nums[mid], sinon lo = mid + 1.
Sinon, la moitié droite est triée : définissez lo = mid + 1 lorsque nums[mid] < target ≤ nums[hi], sinon hi = mid - 1.
Lorsque la boucle se termine, renvoyez -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Pièges et cas limites

Écrire nums[lo] < nums[mid] au lieu de ≤. Lorsqu'il reste deux éléments, mid est égal à lo, et le test strict considère [9, 4] comme une moitié droite triée : target = 4 renvoie -1.
Comparer target à nums[mid] en premier. Dans le premier exemple, avec target = 19, l'élément du milieu, 2, est plus petit ; la recherche se déplace donc vers la droite et manque l'indice 1.
Ne tester qu'une seule extrémité de la moitié triée. Dans [40, 50, 60, 70, 80, 10, 20] avec target = 80, target ≥ nums[lo] à lui seul envoie la recherche dans [40, 50, 60, 70].
En Rust, k - 1 sur un usize provoque un dépassement inférieur lorsque k = 0, c'est-à-dire la liste non pivotée. Utilisez des intervalles semi-ouverts.
En Lua et en R, renvoyer la position indexée à partir de 1. Soustrayez 1.

Questions fréquentes3

Quelle est la complexité temporelle de la recherche dans un tableau trié pivoté ?

Un temps O(log n) et un espace supplémentaire O(1). À chaque étape, on conserve une moitié de l’intervalle, donc 5000 éléments nécessitent au maximum 13 étapes. Trouver d’abord le point de rotation est également en O(log n), avec environ deux fois plus d’étapes.

’algorithme fonctionne-t-il lorsque le tableau contient des doublons ?

Pas tel que c’est écrit. Lorsque nums[lo], nums[mid] et nums[hi] sont égaux, il est impossible de prouver que l’une ou l’autre moitié est triée. La solution habituelle consiste alors à avancer lo d’une position, ce qui préserve la correction de la réponse, mais donne un cas le pire de O(n).

Devez-vous d’abord trouver le point de rotation ou effectuer la recherche en un seul passage ?

Les deux s’exécutent en O(log n). Trouver le minimum revient d’abord à diviser le problème en deux recherches binaires simples. La recherche en un seul passage fait le travail en une seule boucle avec moins d’étapes, et c’est la version à laquelle la plupart des intervieweurs s’attendent.

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

Test #1

Test #2

Test #3

Arguments

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Résultat attendu

Search in Rotated Sorted Array

Fonction

Contraintes

Exemples

Indices

Solution

Parcourir chaque élément

Trouvez le point de rotation, puis effectuez une recherche binaire

Une recherche binaire sur la moitié triée

Pièges et cas limites

Questions fréquentes3

Problèmes similaires