Search in Rotated Sorted Array
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 ne s’y trouve pas, en temps O(log n).
Fonction
- 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-104 ≤ nums[i], target ≤ 104- Toutes les valeurs de
numssont distinctes. numsest une liste croissante pivotée d'un certainkavec0 ≤ k < nums.length;k = 0la laisse non pivotée.
Exemples
- Entrée
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Sortie
- 4
- Explication
- 5 se trouve à l’indice 4. Le premier milieu, l’indice 3, contient 2, donc la moitié droite
[2, 5, 8, 11]est triée, et 5 se trouve entre 2 et 11. Le milieu suivant, l’indice 5, contient 8 ; la partie gauche triée[5, 8]contient 5, ce qui mène à l’indice 4.
- Entrée
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Sortie
- -1
- Explication
- 65 se situerait entre 60 et 70, et aucun élément ne le contient. Le premier élément du milieu, 70 à l’index 3, place 65 dans la partie gauche triée
[40, 50, 60, 70]. La plage se réduit à l’intérieur de cette séquence jusqu’à être vide, donc la fonction renvoie-1.
- 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 ; toute la partie droite est donc abandonnée. La recherche trouve alors 13 à l’indice 1.
+23 tests cachés à la soumission
Pour aller plus loin
Si nums peut contenir des doublons, aucun algorithme ne peut garantir O(log n). Peux-tu le démontrer ? Construis une liste pivotée de 1 avec un seul 0 caché dedans, où toute recherche de 0 doit lire chaque élément.
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Choisis n’importe quel indice du milieu et observe les deux moitiés de part et d’autre. La rotation a créé un endroit où les valeurs diminuent, de la plus grande à la plus petite. Les deux moitiés peuvent-elles contenir cette chute ?
Au moins une moitié est toujours triée, et comparer
nums[lo]avecnums[mid]vous indique laquelle. Pour une moitié triée, vous pouvez vérifier en une étape sitargetse trouve entre sa première et sa dernière valeur.Gardez
loethiautour de la partie qui pourrait encore contenirtarget. À chaque étape, si la plage de valeurs de la moitié triée contienttarget, gardez cette moitié ; sinon, gardez l’autre. Arrêtez-vous lorsque vous trouveztargetou que la plage est vide.
Solution
Une liste triée par rotation se compose de deux séquences triées placées l’une après l’autre : [15, 19, 23], puis [2, 5, 8, 11]. La recherche binaire classique échoue sur cette liste, car comparer target à la valeur du milieu ne permet plus de savoir de quel côté se trouve target. La solution repose sur un fait : quelle que soit la position où vous coupez la liste, au moins l’une des deux moitiés est entièrement triée, et pour une moitié triée, une seule comparaison suffit pour déterminer si target peut s’y trouver.
Parcourir chaque élément
Intuition
Vérifiez chaque indice dans l’ordre et renvoyez le premier dont la valeur est égale à target. Si la boucle se termine sans correspondance, renvoyez -1. Les valeurs sont distinctes, donc la première correspondance est la seule, et le balayage est correct pour toute liste, pivotée ou non.
Cette méthode ignore tout ce que l’énoncé vous indique. La liste est composée de deux séquences triées, mais le balayage peut parcourir les 5000 éléments, alors qu’une recherche binaire nécessite environ 13 comparaisons. L’écart augmente avec la taille de l’entrée : un million d’éléments nécessite un million de comparaisons, contre environ 20. La tâche demande une complexité de O(log n) : cette méthode constitue donc le point de départ à améliorer, pas la réponse.
Algorithme
- Pour chaque indice
ide 0 àn-1, compareznums[i]àtarget. - S’ils sont égaux, renvoyez
i. - Après la boucle, renvoyez
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Trouvez le point de rotation, puis effectuez une recherche binaire
Intuition
La liste pivotée se compose de deux segments triés, et le second commence par la plus petite valeur. Appelons son indice k. Une fois k connu, le problème se ramène à une simple recherche binaire : nums[k..n-1] est trié et contient les valeurs de nums[k] à nums[n-1], et nums[0..k-1] est trié et contient toutes les valeurs supérieures. Une comparaison de target avec nums[k] et nums[n-1] permet de choisir le segment à parcourir.
Pour trouver k, effectuez une recherche binaire sur le point de rupture. Comparez la valeur du milieu avec la dernière valeur de l’intervalle, nums[hi]. Si nums[mid] > nums[hi], les valeurs diminuent quelque part après mid, donc la plus petite valeur se trouve à sa droite : définissez lo = mid + 1. Sinon, nums[mid..hi] augmente sans point de rupture, donc la plus petite valeur se trouve à mid ou avant : définissez hi = mid, en gardant mid dans l’intervalle. Lorsque lo rejoint hi, cet indice est k.
Suivez le premier exemple, [15, 19, 23, 2, 5, 8, 11] avec target = 5. Le 2 du milieu n’est pas supérieur à 11, donc hi devient 3 ; puis 19 est supérieur à 2, donc lo devient 2 ; puis 23 est supérieur à 2, donc lo devient 3, et k = 3. Comme 5 se trouve entre nums[3] = 2 et nums[6] = 11, recherchez dans les indices 3 à 6, où la recherche binaire trouve 5 à l’indice 4. Deux recherches binaires coûtent environ 2 log2 n étapes.
Algorithme
- Définissez
lo = 0ethi = n-1. Tant quelo < hi, calculezmid; sinums[mid] > nums[hi], définissezlo = mid + 1, sinon définissezhi = mid. - Appelez
kl’indice final : il contient la plus petite valeur. - Si
nums[k] ≤ target ≤ nums[n-1], recherchez dans les indiceskàn-1; sinon, recherchez dans les indices 0 àk-1. - Effectuez une recherche binaire classique dans cette plage et renvoyez l’indice de
target, ou-1si la plage devient 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 -1Une recherche binaire sur la moitié triée
Intuition
Tu n’as pas besoin de savoir où se trouve le point de rotation. Garde la promesse habituelle de la recherche binaire : si target figure dans la liste, son indice se trouve entre lo et hi. Examine l’indice du milieu mid. Les valeurs ne diminuent qu’une seule fois dans toute la liste, donc cette baisse se situe dans au plus une des deux moitiés autour de mid, et l’autre moitié est triée.
Repère la moitié triée avec une seule comparaison. Si nums[lo] ≤ nums[mid], la moitié gauche nums[lo..mid] ne contient aucune baisse et est triée. Puisque tu sais déjà que nums[mid] n’est pas target, target ne peut se trouver dans cette moitié que si nums[lo] ≤ target < nums[mid]. Si c’est le cas, définis hi = mid - 1 ; sinon, target ne peut se trouver que dans l’autre moitié, alors définis lo = mid + 1. Lorsque nums[lo] > nums[mid], la baisse se trouve à gauche, la moitié droite nums[mid..hi] est triée, et le test symétrique nums[mid] < target ≤ nums[hi] permet de décider. Tu ne raisonnes jamais directement sur la moitié non triée : target ne s’y trouve que lorsque la moitié triée ne peut pas le contenir.
Suivons le premier exemple, [15, 19, 23, 2, 5, 8, 11] avec target = 5. L’intervalle de 0 à 6 a pour milieu 3, de valeur 2. Comme 15 est supérieur à 2, la moitié droite [2, 5, 8, 11] est triée, et 5 s’y trouve, donc lo devient 4. L’intervalle de 4 à 6 a pour milieu 5, de valeur 8. Maintenant, nums[4] = 5 ≤ 8 : la moitié gauche [5, 8] est triée et contient 5, donc hi devient 4. L’indice 4 contient 5 : renvoie 4.
À chaque étape, l’intervalle est réduit de moitié, comme dans une recherche binaire classique, donc la boucle s’exécute au plus environ log2(n) + 1 fois : 13 étapes pour 5000 éléments, avec deux index de mémoire supplémentaire.
Algorithme
- Définissez
lo = 0ethi = n-1. - Tant que
lo ≤ hi, calculezmid. Sinums[mid]est égal àtarget, renvoyezmid. - Si
nums[lo] ≤ nums[mid], la moitié gauche est triée : sinums[lo] ≤ target < nums[mid], définissezhi = mid - 1, sinon définissezlo = mid + 1. - Sinon, la moitié droite est triée : si
nums[mid] < target ≤ nums[hi], définissezlo = mid + 1, sinon définissezhi = 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
La recherche en un seul passage est courte, et presque tous les bugs se trouvent dans un opérateur de comparaison.
- Écrire
nums[lo] < nums[mid]au lieu de≤. Lorsqu’il reste deux éléments,midest égal àlo, et la moitié gauche contient un élément, qui est trié. Avec le test strict,[9, 4]ettarget = 4considèrent[9, 4]comme la moitié droite triée, cherchent 4 en dehors de l’intervalle de 9 à 4 et renvoient-1. - Comparer d’abord
targetànums[mid], comme dans une recherche binaire classique. Dans[15, 19, 23, 2, 5, 8, 11]avectarget = 19, la valeur centrale 2 est inférieure à 19, donc la recherche se déplace vers la droite et ne voit jamais l’indice 1. - Ne tester qu’une seule extrémité de la moitié triée. Dans
[40, 50, 60, 70, 80, 10, 20]avectarget = 80, la valeur centrale est 70 et la moitié gauche[40, 50, 60, 70]est triée. Le testtarget ≥ nums[lo]à lui seul envoie la recherche à gauche, car 80 est supérieur à 40, mais 80 est aussi supérieur à 70 : il se trouve donc dans la moitié droite. Vérifiez les deux extrémités. - Oublier le cas non pivoté dans l’approche en deux étapes. Lorsque
k = 0, la deuxième exécution est vide et son intervalle va de0à-1. Cela convient avec des indices signés, mais avec des indices non signés (usizede Rust),k - 1provoque un dépassement inférieur, raison pour laquelle le code Rust utilise des intervalles semi-ouverts. - Renvoyer directement la position en Lua et en R. Leurs listes commencent à 1 : soustrayez donc 1 avant de renvoyer le résultat.
Questions fréquentes4
Quelle est la complexité temporelle de la recherche dans un tableau trié pivoté ?
Temps O(log n) et espace supplémentaire O(1). À chaque étape, on conserve une moitié de l’intervalle courant, comme dans une recherche binaire classique, donc une liste de 5000 éléments nécessite au maximum 13 étapes. La version en deux étapes qui trouve d’abord le point de rotation est également en O(log n), avec environ deux fois plus d’étapes.
Comment savoir quelle moitié d’un tableau pivoté est triée ?
Comparez nums[lo] à nums[mid]. Les valeurs ne diminuent qu’une seule fois dans toute la liste. Si nums[lo] ≤ nums[mid], cette baisse ne se trouve pas entre lo et mid, donc la moitié gauche est triée. Sinon, la baisse se trouve dans la moitié gauche, ce qui signifie que la moitié droite, de mid à hi, n’en contient aucune et est triée.
Est-ce que l’algorithme fonctionne lorsque le tableau contient des doublons ?
Pas sous cette forme. Dans [1, 0, 1, 1, 1], nums[lo], nums[mid] et nums[hi] valent tous 1, donc on ne peut prouver qu'aucune des deux moitiés est triée. La solution habituelle consiste à avancer lo d'une position lorsque nums[lo], nums[mid] et nums[hi] sont égaux, ce qui préserve la correction de la réponse, mais donne un pire cas en O(n).
Faut-il d’abord trouver le point de rotation ou effectuer une recherche en un seul passage ?
Les deux s’exécutent en O(log n). Trouver d’abord l’index du minimum divise le problème en deux recherches binaires simples, ce qui permet de réutiliser dans chaque partie du code que tu maîtrises déjà. La recherche en un seul passage fait le même travail dans une seule boucle, avec moins d’étapes, et c’est la version que la plupart des personnes qui te font passer un entretien s’attendent à voir.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def search(nums, target):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Attendu
4