Comment utiliser Advanced Binary Scarch ?

Pourquoi et comment ?

pendant que je résolvais la question sur leetcode qui dit dans un tableau donné de nombres entiers triés par ordre non décroissant, trouvez la position de début et de fin d'une valeur cible donnée. il était donc impossible de renvoyer le début et la fin d'un élément cible dans un tableau avec un simple scarch binaire car il ne renvoie que l'index où il a trouvé le premier élément cible qui peut être n'importe quoi en premier, à la fin ou au milieu de cet élément. nous utilisons donc Double Binary Scarch , et voici comment procéder...

Approche

1. Première recherche binaire :

   • Effectuez une recherche binaire pour trouver la dernière occurrence de la cible.
   • Commencez par si (index de début) à 0 et ei (index de fin) à nums.length - 1.
   • Si l'élément du milieu nums[mid] est inférieur à la cible, déplacez l'index de départ si à mid + 1 pour rechercher dans la moitié droite.
   • S'il est supérieur à la cible, déplacez l'index de fin ei au milieu - 1 pour rechercher dans la moitié gauche.
   • Si nums[mid] est égal à la cible, définissez res[1] sur mid (la fin actuelle de la plage) et continuez à chercher dans la moitié droite (si = mid + 1) pour trouver la dernière occurrence.

2. Deuxième recherche binaire :

   • Effectuez une autre recherche binaire pour trouver la première occurrence de la cible.
   • Réinitialiser si à 0 et ei à nums.length - 1.
   • Suivez une approche similaire à celle précédente, mais si nums[mid] est égal à la cible, définissez res[0] sur mid (le début actuel de la plage) et continuez la recherche dans la moitié gauche (ei = mid - 1) pour trouver la première occurrence.

3. Résultat du retour :

   • Le tableau de résultats res contient les indices de début et de fin de la valeur cible.

Complexité

• Complexité temporelle :

  • La recherche binaire de la première et de la dernière occurrence prend chacune un temps O(log n). Puisque nous effectuons deux recherches binaires, la complexité temporelle globale est O(log n).

• Complexité spatiale :

  • O(1) puisque nous utilisons une quantité fixe d'espace supplémentaire pour les variables.

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[1] = mid;  // Update end index
                si = mid + 1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!