Problème (LeetCode 704)

Étant donné un tableau d'entiers nums trié par ordre croissant contenant n éléments, et un entier target, écrivez une fonction qui recherche target dans nums. Si target existe, retournez son indice ; sinon, retournez -1.

Exemple 1 :
Entrée : nums = [-1,0,3,5,9,12], target = 9
Sortie : 4
Explication : La valeur 9 se trouve à l'indice 4.

Exemple 2 :
Entrée : nums = [-1,0,3,5,9,12], target = 2
Sortie : -1
Explication : La valeur 2 est absente du tableau.

Contraintes :

• Tous les éléments de nums sont uniques.
• n se situe dans l'intervalle [1, 10 000].
• Chaque élément de nums est compris entre -9 999 et 9 999.

Approche algorithmique

La rceherche dichotomique est idéale pour trouver une valeur unique dans un tableau trié. Le principe consiste à réduire itérativement l'intervalle de recherche jusqu'à localiser l'élément cible.

Une implémentation initiale pourrait être :

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int debut = 0;
        int fin = nums.size() - 1;
        while (debut <= fin) {
            int milieu = (debut + fin) / 2;
            if (nums[milieu] > target) {
                fin = milieu - 1;
            } else if (nums[milieu] < target) {
                debut = milieu + 1;
            } else {
                return milieu;
            }
        }
        return -1;
    }
};

Cette version fonctionne, mais présente deux points d'attention critiques :

1. Dépassement de capacité : Le calcul (debut + fin) peut dépasser la limite supérieure d'un entier (INT_MAX) si les indices sont très grands.
2. Gestion de l'intervalle : La condition d'arrêt et la mise à jour des bornes dépendent du type d'intervalle choisi (fermé-fermé ou fermé-ouvert).

Implémentation robuste

Voici deux variantes corrigées et commentées.

1. Intervalle fermé-fermé [gauche, droite]

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int gauche = 0;
        int droite = nums.size() - 1;
        while (gauche <= droite) {
            // Calcul sûr du milieu pour éviter le dépassement
            int milieu = gauche + (droite - gauche) / 2;
            if (nums[milieu] == target) {
                return milieu;
            } else if (nums[milieu] < target) {
                gauche = milieu + 1;
            } else {
                droite = milieu - 1;
            }
        }
        return -1;
    }
};

2. Intervalle fermé-ouvert [gauche, droite)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int gauche = 0;
        int droite = nums.size();
        while (gauche < droite) {
            int milieu = gauche + (droite - gauche) / 2;
            if (nums[milieu] == target) {
                return milieu;
            } else if (nums[milieu] < target) {
                gauche = milieu + 1;
            } else {
                // Réduire l'intervalle à [gauche, milieu)
                droite = milieu;
            }
        }
        return -1;
    }
};

Points clés à retenir

• La recherche dichotomique nécessite un tableau trié.
• La cohérence dans la définition de l'intervalle (fermé-fermé ou fermé-ouvert) est fondamentale pour la mise à jour correcte des bornes.
• Pour calculer l'indice médian de manière sûre, privilégiez la formule gauche + (droite - gauche) / 2 ou son équivalent par décalage de bits : gauche + ((droite - gauche) >> 1).