Recherche de tableaux dans DSA à l'aide de JavaScript : des bases à l'avancée

La recherche de tableaux est un concept fondamental dans les structures de données et les algorithmes (DSA). Cet article de blog couvrira diverses techniques de recherche de tableaux utilisant JavaScript, allant des niveaux de base aux niveaux avancés. Nous explorerons 20 exemples, discuterons des complexités temporelles et proposerons des problèmes LeetCode pour la pratique.

Table des matières

1. Recherche linéaire
2. Recherche binaire
3. Recherche sautée
4. Recherche d'interpolation
5. Recherche exponentielle
6. Recherche de sous-tableaux
7. Technique à deux pointeurs
8. Technique de la fenêtre coulissante
9. Techniques de recherche avancées
10. Problèmes de pratique LeetCode

1. Recherche linéaire

La recherche linéaire est l'algorithme de recherche le plus simple qui fonctionne à la fois sur les tableaux triés et non triés.

Complexité temporelle : O(n), où n est le nombre d'éléments dans le tableau.

Exemple 1 : Recherche linéaire de base

function linearSearch(arr, target) {
    for (let i = 0; i 



<h3>
  
  
  Exemple 2 : Rechercher toutes les occurrences
</h3>



<pre class="brush:php;toolbar:false">function findAllOccurrences(arr, target) {
    const result = [];
    for (let i = 0; i 



<h2>
  
  
  2. Recherche binaire
</h2>

<p>La recherche binaire est un algorithme efficace pour rechercher dans des tableaux triés.</p>

<p><strong>Complexité temporelle :</strong> O(log n)</p>

<h3>
  
  
  Exemple 3 : Recherche binaire itérative
</h3>



<pre class="brush:php;toolbar:false">function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left 



<h3>
  
  
  Exemple 4 : Recherche binaire récursive
</h3>



<pre class="brush:php;toolbar:false">function recursiveBinarySearch(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1;
    }

    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] 



<h2>
  
  
  3. Recherche sautée
</h2>

<p>La recherche sautée est un algorithme pour les tableaux triés qui fonctionne en sautant certains éléments pour réduire le nombre de comparaisons.</p>

<p><strong>Complexité temporelle :</strong> O(√n)</p>

<h3>
  
  
  Exemple 5 : implémentation de la recherche sautée
</h3>



<pre class="brush:php;toolbar:false">function jumpSearch(arr, target) {
    const n = arr.length;
    const step = Math.floor(Math.sqrt(n));
    let prev = 0;

    while (arr[Math.min(step, n) - 1] = n) {
            return -1;
        }
    }

    while (arr[prev] 



<h2>
  
  
  4. Recherche d'interpolation
</h2>

<p>La recherche par interpolation est une variante améliorée de la recherche binaire pour les tableaux triés uniformément distribués.</p>

<p><strong>Complexité temporelle :</strong> O(log log n) pour des données uniformément distribuées, O(n) dans le pire des cas.</p>

<h3>
  
  
  Exemple 6 : Implémentation de la recherche par interpolation
</h3>



<pre class="brush:php;toolbar:false">function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low = arr[low] && target 



<h2>
  
  
  5. Recherche exponentielle
</h2>

<p>La recherche exponentielle est utile pour les recherches illimitées et fonctionne également bien pour les tableaux limités.</p>

<p><strong>Complexité temporelle :</strong> O(log n)</p>

<h3>
  
  
  Exemple 7 : implémentation de la recherche exponentielle
</h3>



<pre class="brush:php;toolbar:false">function exponentialSearch(arr, target) {
    if (arr[0] === target) {
        return 0;
    }

    let i = 1;
    while (i 



<h2>
  
  
  6. Recherche de sous-tableaux
</h2>

<p>La recherche de sous-tableaux au sein d'un tableau plus grand est un problème courant dans DSA.</p>

<h3>
  
  
  Exemple 8 : Recherche naïve de sous-tableaux
</h3>

<p><strong>Complexité temporelle :</strong> O(n * m), où n est la longueur du tableau principal et m est la longueur du sous-tableau.<br>
</p>

<pre class="brush:php;toolbar:false">function naiveSubarraySearch(arr, subArr) {
    for (let i = 0; i 



<h3>
  
  
  Exemple 9 : algorithme KMP pour la recherche de sous-tableaux
</h3>

<p><strong>Complexité temporelle :</strong> O(n + m)<br>
</p>

<pre class="brush:php;toolbar:false">function kmpSearch(arr, pattern) {
    const n = arr.length;
    const m = pattern.length;
    const lps = computeLPS(pattern);
    let i = 0, j = 0;

    while (i 



<h2>
  
  
  7. Technique à deux pointeurs
</h2>

<p>La technique à deux pointeurs est souvent utilisée pour rechercher dans des tableaux triés ou lorsqu'il s'agit de paires.</p>

<h3>
  
  
  Exemple 10 : Trouver une paire avec une somme donnée
</h3>

<p><strong>Complexité temporelle :</strong> O(n)<br>
</p>

<pre class="brush:php;toolbar:false">function findPairWithSum(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left 



<h3>
  
  
  Exemple 11 : Problème à trois sommes
</h3>

<p><strong>Complexité temporelle :</strong> O(n^2)<br>
</p>

<pre class="brush:php;toolbar:false">function threeSum(arr, target) {
    arr.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i  0 && arr[i] === arr[i - 1]) continue;

        let left = i + 1;
        let right = arr.length - 1;

        while (left 



<h2>
  
  
  8. Technique de la fenêtre coulissante
</h2>

<p>La technique de la fenêtre coulissante est utile pour résoudre des problèmes de tableau/chaîne avec des éléments contigus.</p>

<h3>
  
  
  Exemple 12 : Sous-tableau de somme maximale de taille K
</h3>

<p><strong>Complexité temporelle :</strong> O(n)<br>
</p>

<pre class="brush:php;toolbar:false">function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    for (let i = 0; i 



<h3>
  
  
  Exemple 13 : sous-chaîne la plus longue avec K caractères distincts
</h3>

<p><strong>Complexité temporelle :</strong> O(n)<br>
</p>

<pre class="brush:php;toolbar:false">function longestSubstringKDistinct(s, k) {
    const charCount = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right  k) {
            charCount.set(s[left], charCount.get(s[left]) - 1);
            if (charCount.get(s[left]) === 0) {
                charCount.delete(s[left]);
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

const s = "aabacbebebe";
console.log(longestSubstringKDistinct(s, 3)); // Output: 7

9. Techniques de recherche avancées

Exemple 14 : Recherche dans un tableau trié avec rotation

Complexité temporelle : O(log n)

function searchRotatedArray(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left = arr[left] && target  arr[mid] && target 



<h3>
  
  
  Exemple 15 : Recherche dans une matrice 2D
</h3>

<p><strong>Complexité temporelle :</strong> O(log(m * n)), où m est le nombre de lignes et n est le nombre de colonnes<br>
</p>

<pre class="brush:php;toolbar:false">function searchMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;

    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n - 1;

    while (left 



<h3>
  
  
  Exemple 16 : Trouver un élément de pointe
</h3>

<p><strong>Complexité temporelle :</strong> O(log n)<br>
</p>

<pre class="brush:php;toolbar:false">function findPeakElement(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left  arr[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

const arr = [1, 2, 1, 3, 5, 6, 4];
console.log(findPeakElement(arr)); // Output: 5

Exemple 17 : Recherche dans un tableau trié de taille inconnue

Complexité temporelle : O(log n)

function searchUnknownSize(arr, target) {
    let left = 0;
    let right = 1;

    while (arr[right] 



<h3>
  
  
  Exemple 18 : Rechercher le minimum dans un tableau trié avec rotation
</h3>

<p><strong>Complexité temporelle :</strong> O(log n)<br>
</p>

<pre class="brush:php;toolbar:false">function findMin(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left  arr[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return arr[left];
}

const rotatedArr = [4, 5, 6, 7, 0, 1, 2];
console.log(findMin(rotatedArr)); // Output: 0

Exemple 19 : Rechercher une plage

Complexité temporelle : O(log n)

function searchRange(arr, target) {
    const left = findBound(arr, target, true);
    if (left === -1) return [-1, -1];
    const right = findBound(arr, target, false);
    return [left, right];
}

function findBound(arr, target, isLeft) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left 



<h3>
  
  
  Exemple 20 : Médiane de deux tableaux triés
</h3>

<p><strong>Complexité temporelle :</strong> O(log(min(m, n))), où m et n sont les longueurs des deux tableaux<br>
</p>

<pre class="brush:php;toolbar:false">function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    const m = nums1.length;
    const n = nums2.length;
    let left = 0;
    let right = m;

    while (left  minRightY) {
            right = partitionX - 1;
        } else {
            left = partitionX + 1;
        }
    }
    throw new Error("Input arrays are not sorted.");
}

const nums1 = [1, 3];
const nums2 = [2];
console.log(findMedianSortedArrays(nums1, nums2)); // Output: 2

10. Problèmes de pratique de LeetCode

Pour tester davantage votre compréhension et vos compétences en matière de recherche de tableaux, voici 15 problèmes LeetCode que vous pouvez pratiquer :

1. Zwei Summe
2. Suche in gedrehter sortierter Anordnung
3. Minimum im gedrehten sortierten Array finden
4. Eine 2D-Matrix durchsuchen
5. Spitzenelement finden
6. Nach einem Bereich suchen
7. Median von zwei sortierten Arrays
8. K-tes größtes Element in einem Array
9. Finden Sie K nächstgelegene Elemente
10. Suche in einem sortierten Array unbekannter Größe
11. Kapazität, Pakete innerhalb von D Tagen zu versenden
12. Koko isst Bananen
13. Suchen Sie die doppelte Nummer
14. Längste Teilzeichenfolge mit höchstens K unterschiedlichen Zeichen
15. Subarray-Summe gleich K

Diese Probleme decken ein breites Spektrum an Array-Suchtechniken ab und werden Ihnen dabei helfen, Ihr Verständnis der in diesem Blogbeitrag besprochenen Konzepte zu festigen.

Zusammenfassend lässt sich sagen, dass die Beherrschung von Array-Suchtechniken entscheidend ist, um sich mit Datenstrukturen und Algorithmen vertraut zu machen. Wenn Sie diese verschiedenen Methoden verstehen und implementieren, sind Sie besser für die Bewältigung komplexer Probleme und die Optimierung Ihres Codes gerüstet. Denken Sie daran, die zeitliche und räumliche Komplexität jedes Ansatzes zu analysieren und basierend auf den spezifischen Anforderungen Ihres Problems den am besten geeigneten auszuwählen.

Viel Spaß beim Codieren und Suchen!

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!