Carian Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan

Pencarian tatasusunan ialah konsep asas dalam Struktur Data dan Algoritma (DSA). Catatan blog ini akan merangkumi pelbagai teknik carian tatasusunan menggunakan JavaScript, dari peringkat asas hingga lanjutan. Kami akan meneroka 20 contoh, membincangkan kerumitan masa dan menyediakan masalah LeetCode untuk latihan.

Jadual Kandungan

1. Carian Linear
2. Carian Binari
3. Lompat Cari
4. Carian Interpolasi
5. Carian Eksponen
6. Carian Subarray
7. Teknik Dua Penunjuk
8. Teknik Tingkap Gelongsor
9. Teknik Carian Terperinci
10. Masalah Amalan LeetCode

1. Carian Linear

Carian linear ialah algoritma carian paling mudah yang berfungsi pada tatasusunan yang diisih dan tidak diisih.

Kerumitan Masa: O(n), dengan n ialah bilangan elemen dalam tatasusunan.

Contoh 1: Carian Linear Asas

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



<h3>
  
  
  Contoh 2: Cari Semua Kejadian
</h3>



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



<h2>
  
  
  2. Carian Binari
</h2>

<p>Carian binari ialah algoritma yang cekap untuk mencari dalam tatasusunan yang diisih.</p>

<p><strong>Kerumitan Masa:</strong> O(log n)</p>

<h3>
  
  
  Contoh 3: Carian Binari Berulang
</h3>



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

    while (left 



<h3>
  
  
  Contoh 4: Carian Binari Rekursif
</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. Lompat Carian
</h2>

<p>Carian lompat ialah algoritma untuk tatasusunan diisih yang berfungsi dengan melangkau beberapa elemen untuk mengurangkan bilangan perbandingan.</p>

<p><strong>Kerumitan Masa:</strong> O(√n)</p>

<h3>
  
  
  Contoh 5: Pelaksanaan Carian Lompat
</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. Carian Interpolasi
</h2>

<p>Carian interpolasi ialah varian carian binari yang dipertingkatkan untuk tatasusunan diisih yang diedarkan secara seragam.</p>

<p><strong>Kerumitan Masa:</strong> O(log log n) untuk data teragih seragam, O(n) dalam kes yang paling teruk.</p>

<h3>
  
  
  Contoh 6: Pelaksanaan Carian Interpolasi
</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. Carian Eksponen
</h2>

<p>Carian eksponen berguna untuk carian tanpa sempadan dan berfungsi dengan baik untuk tatasusunan terhad juga.</p>

<p><strong>Kerumitan Masa:</strong> O(log n)</p>

<h3>
  
  
  Contoh 7: Pelaksanaan Carian Eksponen
</h3>



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

    let i = 1;
    while (i 



<h2>
  
  
  6. Carian Subarray
</h2>

<p>Mencari subarray dalam tatasusunan yang lebih besar ialah masalah biasa dalam DSA.</p>

<h3>
  
  
  Contoh 8: Carian Subarray Naif
</h3>

<p><strong>Kerumitan Masa:</strong> O(n * m), dengan n ialah panjang tatasusunan utama dan m ialah panjang subarray.<br>
</p>

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



<h3>
  
  
  Contoh 9: Algoritma KMP untuk Carian Subarray
</h3>

<p><strong>Kerumitan Masa:</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. Teknik Dua Penunjuk
</h2>

<p>Teknik dua mata sering digunakan untuk mencari dalam tatasusunan yang disusun atau apabila berurusan dengan pasangan.</p>

<h3>
  
  
  Contoh 10: Cari Pasangan dengan Jumlah Diberi
</h3>

<p><strong>Kerumitan Masa:</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>
  
  
  Contoh 11: Masalah Jumlah Tiga
</h3>

<p><strong>Kerumitan Masa:</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. Teknik Tingkap Gelongsor
</h2>

<p>Teknik tetingkap gelongsor berguna untuk menyelesaikan masalah tatasusunan/rentetan dengan elemen bersebelahan.</p>

<h3>
  
  
  Contoh 12: Subarray Jumlah Maksimum Saiz K
</h3>

<p><strong>Kerumitan Masa:</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>
  
  
  Contoh 13: Subrentetan Terpanjang dengan Aksara K Distinct
</h3>

<p><strong>Kerumitan Masa:</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. Teknik Carian Lanjutan

Contoh 14: Cari dalam Tatasusunan Isih Diputar

Kerumitan Masa: O(log n)

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

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



<h3>
  
  
  Contoh 15: Cari dalam Matriks 2D
</h3>

<p><strong>Kerumitan Masa:</strong> O(log(m * n)), dengan m ialah bilangan baris dan n ialah bilangan lajur<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>
  
  
  Contoh 16: Cari Elemen Puncak
</h3>

<p><strong>Kerumitan Masa:</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

Contoh 17: Cari dalam Susunan Isih Saiz Tidak Diketahui

Kerumitan Masa: O(log n)

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

    while (arr[right] 



<h3>
  
  
  Contoh 18: Cari Minimum dalam Tatasusunan Isih Diputar
</h3>

<p><strong>Kerumitan Masa:</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

Contoh 19: Cari Julat

Kerumitan Masa: 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>
  
  
  Contoh 20: Median Dua Tatasusunan Isih
</h3>

<p><strong>Kerumitan Masa:</strong> O(log(min(m, n))), dengan m dan n ialah panjang dua tatasusunan<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. Masalah Amalan LeetCode

Untuk menguji lagi pemahaman dan kemahiran anda dalam pencarian tatasusunan, berikut ialah 15 masalah LeetCode yang boleh anda amalkan:

1. Deux sommes
2. Recherche dans un tableau trié avec rotation
3. Trouver le minimum dans un tableau trié avec rotation
4. Rechercher une matrice 2D
5. Trouver l'élément de pointe
6. Rechercher une plage
7. Médiane de deux tableaux triés
8. Kième plus grand élément d'un tableau
9. Trouver les éléments les plus proches
10. Rechercher dans un tableau trié de taille inconnue
11. Capacité d'expédition des colis sous les jours J
12. Koko mange des bananes
13. Trouver le numéro en double
14. Sous-chaîne la plus longue avec au plus K caractères distincts
15. La somme du sous-tableau est égale à K

Ces problèmes couvrent un large éventail de techniques de recherche de tableaux et vous aideront à consolider votre compréhension des concepts abordés dans cet article de blog.

En conclusion, maîtriser les techniques de recherche de tableaux est crucial pour maîtriser les structures de données et les algorithmes. En comprenant et en mettant en œuvre ces différentes méthodes, vous serez mieux équipé pour résoudre des problèmes complexes et optimiser votre code. N'oubliez pas d'analyser la complexité temporelle et spatiale de chaque approche et de choisir la plus appropriée en fonction des exigences spécifiques de votre problématique.

Bon codage et bonne recherche !

Atas ialah kandungan terperinci Carian Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!