简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
首頁 > web前端 > js教程 > 主體

使用 JavaScript 在 DSA 中進行數組搜尋：從基礎到高級

WBOY
發布： 2024-09-04 22:47:32
原創
431 人瀏覽過

Array Searching in DSA using JavaScript: From Basics to Advanced

陣列搜尋是資料結構和演算法（DSA）中的基本概念。這篇部落格文章將介紹使用 JavaScript 的各種陣列搜尋技術，從基礎到進階。我們將探索 20 個範例，討論時間複雜度，並提供 LeetCode 練習題。

目錄

  1. 線性搜尋
  2. 二分查找
  3. 跳轉搜尋
  4. 插值搜尋
  5. 指數搜尋
  6. 子數組搜尋
  7. 雙指針技術
  8. 滑動視窗技術
  9. 進階搜尋技術
  10. LeetCode 練習題

1. 線性搜索

線性搜尋是最簡單的搜尋演算法，適用於排序和未排序的陣列。

時間複雜度： O(n)，其中 n 是陣列中的元素數量。

範例 1：基本線性搜尋 

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

const arr = [5, 2, 8, 12, 1, 6];
console.log(linearSearch(arr, 8)); // Output: 2
console.log(linearSearch(arr, 3)); // Output: -1
登入後複製

範例 2：尋找所有出現的情況 

function findAllOccurrences(arr, target) {
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            result.push(i);
        }
    }
    return result;
}

const arr = [1, 2, 3, 4, 2, 5, 2, 6];
console.log(findAllOccurrences(arr, 2)); // Output: [1, 4, 6]
登入後複製

2.二分查找

二分搜尋是一種在排序數組中搜尋的有效演算法。

時間複雜度： O(log n)

範例 3：迭代二分搜尋 

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

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

const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArr, 7)); // Output: 3
console.log(binarySearch(sortedArr, 10)); // Output: -1
登入後複製

範例 4：遞歸二分查找 

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] < target) {
        return recursiveBinarySearch(arr, target, mid + 1, right);
    } else {
        return recursiveBinarySearch(arr, target, left, mid - 1);
    }
}

const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(recursiveBinarySearch(sortedArr, 13)); // Output: 6
console.log(recursiveBinarySearch(sortedArr, 4)); // Output: -1
登入後複製

3. 跳轉搜索

跳躍搜尋是一種排序數組演算法，它透過跳過一些元素來減少比較次數。

時間複雜度： O(√n)

範例 5：跳轉搜尋實現 

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] < target) {
        prev = step;
        step += Math.floor(Math.sqrt(n));
        if (prev >= n) {
            return -1;
        }
    }

    while (arr[prev] < target) {
        prev++;
        if (prev === Math.min(step, n)) {
            return -1;
        }
    }

    if (arr[prev] === target) {
        return prev;
    }
    return -1;
}

const sortedArr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377];
console.log(jumpSearch(sortedArr, 55)); // Output: 10
console.log(jumpSearch(sortedArr, 111)); // Output: -1
登入後複製

4.插值搜索

插值搜尋是針對均勻分佈排序數組的二分搜尋的改進變體。

時間複雜度： 對於均勻分佈的數據，O(log log n)，最壞情況下為 O(n)。

範例 6：插值搜尋實現 

function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low === high) {
            if (arr[low] === target) return low;
            return -1;
        }

        const pos = low + Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]));

        if (arr[pos] === target) {
            return pos;
        } else if (arr[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    return -1;
}

const uniformArr = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
console.log(interpolationSearch(uniformArr, 64)); // Output: 6
console.log(interpolationSearch(uniformArr, 100)); // Output: -1
登入後複製

5. 指數搜尋

指數搜尋對於無界搜尋很有用，也適用於有界數組。

時間複雜度： O(log n)

範例 7：指數搜尋實現 

function exponentialSearch(arr, target) {
    if (arr[0] === target) {
        return 0;
    }

    let i = 1;
    while (i < arr.length && arr[i] <= target) {
        i *= 2;
    }

    return binarySearch(arr, target, i / 2, Math.min(i, arr.length - 1));
}

function binarySearch(arr, target, left, right) {
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
console.log(exponentialSearch(sortedArr, 7)); // Output: 6
console.log(exponentialSearch(sortedArr, 16)); // Output: -1
登入後複製

6. 子數組搜索

在較大數組中搜尋子數組是 DSA 中的常見問題。

範例 8：樸素子數組搜索

時間複雜度： O(n * m)，其中 n 是主數組的長度，m 是子數組的長度。 

function naiveSubarraySearch(arr, subArr) {
    for (let i = 0; i <= arr.length - subArr.length; i++) {
        let j;
        for (j = 0; j < subArr.length; j++) {
            if (arr[i + j] !== subArr[j]) {
                break;
            }
        }
        if (j === subArr.length) {
            return i;
        }
    }
    return -1;
}

const mainArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const subArr = [3, 4, 5];
console.log(naiveSubarraySearch(mainArr, subArr)); // Output: 2
登入後複製

範例 9：用於子數組搜尋的 KMP 演算法

時間複雜度： O(n + m)

function kmpSearch(arr, pattern) {
    const n = arr.length;
    const m = pattern.length;
    const lps = computeLPS(pattern);
    let i = 0, j = 0;

    while (i < n) {
        if (pattern[j] === arr[i]) {
            i++;
            j++;
        }

        if (j === m) {
            return i - j;
        } else if (i < n && pattern[j] !== arr[i]) {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

function computeLPS(pattern) {
    const m = pattern.length;
    const lps = new Array(m).fill(0);
    let len = 0;
    let i = 1;

    while (i < m) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

const mainArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const pattern = [3, 4, 5];
console.log(kmpSearch(mainArr, pattern)); // Output: 2
登入後複製

7. 兩指針技術

兩指標技術通常用於在排序數組中搜尋或處理對時。

範例 10：尋找具有給定總和的對

時間複雜度： O(n)

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

    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [-1, -1];
}

const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(findPairWithSum(sortedArr, 10)); // Output: [3, 7]
登入後複製

例 11：三和問題

時間複雜度： O(n^2)

function threeSum(arr, target) {
    arr.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < arr.length - 2; i++) {
        if (i > 0 && arr[i] === arr[i - 1]) continue;

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

        while (left < right) {
            const sum = arr[i] + arr[left] + arr[right];
            if (sum === target) {
                result.push([arr[i], arr[left], arr[right]]);
                while (left < right && arr[left] === arr[left + 1]) left++;
                while (left < right && arr[right] === arr[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

const arr = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(arr, 0)); // Output: [[-1, -1, 2], [-1, 0, 1]]
登入後複製

8. 滑動視窗技術

滑動視窗技術對於解決具有連續元素的陣列/字串問題非常有用。

範例 12：大小為 K 的最大和子數組

時間複雜度： O(n)

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

const arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39
登入後複製

範例 13：具有 K 個不同字元的最長子字串

時間複雜度： O(n)

function longestSubstringKDistinct(s, k) {
    const charCount = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        charCount.set(s[right], (charCount.get(s[right]) || 0) + 1);

        while (charCount.size > 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. 進階搜尋技術

範例 14：在旋轉排序數組中搜尋

時間複雜度： O(log n)

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

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        }

        if (arr[left] <= arr[mid]) {
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

const rotatedArr = [4, 5, 6, 7, 0, 1, 2];
console.log(searchRotatedArray(rotatedArr, 0)); // Output: 4
登入後複製

範例 15：在 2D 矩陣中搜尋

時間複雜度： O(log(m * n))，其中 m 是行數，n 是列數

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 <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = matrix[Math.floor(mid / n)][mid % n];

        if (midValue === target) {
            return true;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

const matrix = [
    [1,   3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
];
console.log(searchMatrix(matrix, 3)); // Output: true
登入後複製

範例 16：尋找峰值元素

時間複雜度： O(log n)

function findPeakElement(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] > 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
登入後複製

範例 17：在未知大小的排序數組中搜尋

時間複雜度： O(log n)

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

    while (arr[right] < target) {
        left = right;
        right *= 2;
    }

    return binarySearch(arr, target, left, right);
}

function binarySearch(arr, target, left, right) {
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Assume we have a special array that throws an error when accessing out-of-bounds elements
const specialArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
console.log(searchUnknownSize(specialArray, 7)); // Output: 6
登入後複製

範例 18：找出旋轉排序數組中的最小值

時間複雜度： O(log n)

function findMin(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] > 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
登入後複製

範例 19：搜尋範圍

時間複雜度： 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 <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            result = mid;
            if (isLeft) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

const arr = [5, 7, 7, 8, 8, 10];
console.log(searchRange(arr, 8)); // Output: [3, 4]
登入後複製

範例 20：兩個排序數組的中位數

時間複雜度： O(log(min(m, n)))，其中 m 和 n 是兩個陣列的長度

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 <= right) {
        const partitionX = Math.floor((left + right) / 2);
        const partitionY = Math.floor((m + n + 1) / 2) - partitionX;

        const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        const minRightX = partitionX === m ? Infinity : nums1[partitionX];
        const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        const minRightY = partitionY === n ? Infinity : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > 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.LeetCode練習題

為了進一步測試您對陣列搜尋的理解和技能，您可以練習以下 15 個 LeetCode 問題：

  1. 兩和
  2. 在旋轉排序數組中搜尋
  3. 找出旋轉排序數組中的最小值
  4. 搜尋二維矩陣
  5. 找出峰值元素
  6. 搜尋範圍
  7. 兩個排序數組的中位數
  8. 陣列中的第 K 個最大元素
  9. 找 K 個最接近的元素
  10. 在未知大小的排序數組中搜尋
  11. D 天內運送包裹的能力
  12. 科科吃香蕉
  13. 找重複的數字
  14. 最多包含 K 個不同字元的最長子字串
  15. 子數組和等於 K

這些問題涵蓋了廣泛的陣列搜尋技術，並將幫助您鞏固對本部落格文章中討論的概念的理解。

總之，掌握數組搜尋技術對於精通資料結構和演算法至關重要。透過理解和實現這些不同的方法，您將能夠更好地解決複雜的問題並優化您的程式碼。請記住分析每種方法的時間和空間複雜度，並根據您問題的特定要求選擇最合適的一種。

祝您編碼和搜尋愉快！

以上是使用 JavaScript 在 DSA 中進行數組搜尋：從基礎到高級的詳細內容。更多資訊請關注PHP中文網其他相關文章！

來源：dev.to
上一篇：模擬請求 下一篇：適合前端開發人員的最佳 JavaScript 框架
本網站聲明
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
作者最新文章
最新問題
function_exists()無法判定自訂函數 function test()    {        return true;    }    if (function_exists('TEST')) {        ech...
來自於 2024-04-29 11:01:01
0
2
1318
google 瀏覽器 手機版顯示的怎麼實現 老師您好，google 瀏覽器怎麼變成手機版樣式的？
來自於 2024-04-23 00:22:19
0
9
1421
子窗口操作父窗口，輸出沒反應 前兩句可執行，最後一句沒辦法應
來自於 2024-04-19 15:37:47
0
1
1245
父視窗沒有輸出 document.onclick = function(){ window.opener.document.write('我是子視窗的輸出');                  ...
來自於 2024-04-18 23:52:34
0
1
1149
關於CSS心智圖的課件在哪？ 課件
來自於 2024-04-16 10:10:18
0
0
1230
相關專題
更多>
熱門推薦
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網：公益線上PHP培訓，幫助PHP學習者快速成長！