Recherche binaire dans des tableaux pivotés et non triés

Un tableau trié pivoté est un tableau trié qui a été coupé à un certain pivot, puis dont les deux parties ont été interverties. Par exemple, [4, 5, 6, 7, 0, 1, 2] est le tableau trié [0,1,2,4,5,6,7] pivoté à l’indice 4. La recherche binaire standard échoue dans ce cas, car le tableau n’est plus trié globalement.

L’idée essentielle est qu’au moins une moitié du tableau est toujours triée après toute rotation. Votre recherche binaire doit déterminer quelle moitié est triée avant de décider comment déplacer les bornes.

Après avoir calculé mid, comparez arr[lo] à arr[mid]. Si arr[lo] <= arr[mid], la moitié gauche est triée ; sinon, la moitié droite est triée. Une fois que vous savez quelle moitié est triée, vous pouvez vérifier si la cible appartient à cette plage triée et restreindre la recherche en conséquence.

Cet arbre de décision vous permet d’éliminer exactement la moitié du tableau à chaque étape, tout en conservant la complexité O(log n), même dans un tableau ayant subi une rotation.

Suivons pas à pas l’exécution de search_rotated([4,5,6,7,0,1,2], 0). Au départ, lo=0, hi=6, mid=3, arr[mid]=7. La cible 0 se trouve-t-elle dans la moitié gauche triée [4..7] ? Non, nous définissons donc lo=4. À présent, lo=4, hi=6, mid=5, arr[mid]=1. La moitié gauche [0,1] est triée (arr[lo]=0 <= arr[mid]=1). 0 se trouve-t-il dans [0..1) ? Oui, nous définissons donc hi=4. À présent, lo=4, hi=4, mid=4, arr[4]=0 — trouvé à l’indice 4.

Lorsque le tableau ayant subi une rotation peut contenir des doublons (par exemple, [1,3,1,1,1]), la condition nums[lo] == nums[mid] est ambiguë : vous ne pouvez pas déterminer quelle moitié est triée. La solution sûre consiste à incrémenter lo (ou à décrémenter hi) d’une unité, puis à réessayer. Dans le pire des cas, cela dégrade le temps d’exécution à O(n), ce que vous devez mentionner à la personne qui vous interroge.

Un problème connexe consiste à trouver le plus petit élément d’un tableau trié après rotation, sans rechercher une cible précise. Le minimum se trouve toujours dans la moitié non triée. À chaque étape : si arr[mid] > arr[hi], le minimum se trouve dans la moitié droite (lo = mid + 1) ; sinon, il se trouve dans la moitié gauche, en incluant mid (hi = mid). Lorsque lo == hi, vous avez trouvé le minimum.

La condition arr[lo] <= arr[mid] fonctionne car, dans un segment trié (ou trié sans rotation), le premier élément est toujours le plus petit. Si arr[lo] <= arr[mid], aucune rotation n’a eu lieu dans [lo..mid] ; cette moitié est donc triée. L’égalité prend en charge le cas où lo == mid (un segment à un seul élément est naturellement trié).

Inversement, si arr[lo] > arr[mid], le pivot de rotation doit se trouver entre lo et mid, ce qui signifie que la moitié droite [mid..hi] constitue le segment trié contigu.

La recherche binaire dans un tableau trié après rotation conserve un temps d’exécution de O(log n) et un espace de O(1), car nous divisons toujours l’espace de recherche par deux à chaque itération. La seule différence par rapport à la recherche binaire classique est une vérification supplémentaire en temps constant pour déterminer quelle moitié est triée.

Avec des doublons, le pire des cas se dégrade à O(n), car nous pouvons n’incrémenter lo que d’une unité à chaque étape. Mentionnez explicitement ce compromis : cela montre que vous réfléchissez aux cas limites au-delà du chemin nominal.

LeetCode 33, « Recherche dans un tableau trié après rotation », est la forme canonique de ce problème. Les contraintes garantissent l’absence de doublons et exactement une rotation. La solution est la fonction search_rotated que nous avons écrite précédemment. Points clés pour l’entretien : énoncez toujours l’hypothèse d’absence de doublons, vérifiez vos inégalités avec un exemple concret à la limite, et confirmez que l’indice renvoyé est correct, que la cible soit trouvée ou non.

LeetCode 153, « Trouver le minimum dans un tableau trié après rotation », demande de trouver le minimum sans doublons. L’approche consiste à comparer arr[mid] à arr[hi] (et non à arr[lo]) pour déterminer de quel côté se trouve le minimum. Si arr[mid] > arr[hi], le minimum se trouve à droite ; sinon, il se trouve à mid ou à gauche. Cette méthode converge vers le minimum en O(log n).

Une fois que vous savez trouver le plus petit élément, vous connaissez également le nombre de rotations : l’indice du minimum correspond exactement au nombre de positions dont le tableau a été décalé vers la droite. Par exemple, dans [4,5,6,7,0,1,2], le minimum se trouve à l’indice 4 ; le tableau a donc subi une rotation de 4 positions.

Connaître le pivot vous permet d’appliquer une recherche binaire standard en considérant les indices modulo n : real_idx = (mid + pivot) % n. Cette autre formulation peut simplifier le raisonnement lorsque vous travaillez avec des structures indexées circulairement.

Lorsque vous rencontrez un problème de tableau ayant subi une rotation en entretien, suivez cet arbre de décision. Commencez par déterminer si vous devez trouver une cible ou trouver le minimum. Pour trouver une cible, utilisez l’approche d’identification de la moitié triée. Pour trouver le minimum, comparez mid à hi. Si des doublons sont possibles, mentionnez le pire cas O(n) et ajoutez une solution de repli consistant à resserrer les bornes.

Entraînez-vous en suivant l’exécution de votre code sur les trois exemples classiques : aucune rotation, une rotation, et une rotation plaçant le minimum à la dernière position.

Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.

Dans cette leçon, vous avez appris que : un tableau trié après rotation possède toujours au moins une moitié triée, il faut comparer arr[lo] à arr[mid] pour déterminer quelle moitié est triée avant de décider où chercher, et la recherche du minimum utilise arr[mid] par rapport à arr[hi] pour localiser le pivot de rotation. Ensuite, nous découvrirons les variantes de recherche binaire avec borne inférieure et borne supérieure.