JavaScript を使用した DSA での配列検索: 基本から高度まで

配列検索は、データ構造とアルゴリズム (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. ツーポインターテクニック

2 ポインター手法は、ソートされた配列内の検索やペアを扱う場合によく使用されます。

例 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: 3 つの和の問題

時間計算量: 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: ソートされた 2 つの配列の中央値

時間計算量: O(log(min(m, n)))、ここで、m と n は 2 つの配列の長さです

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. 2D 매트릭스 검색
5. 피크 요소 찾기
6. 범위 검색
7. 두 개의 정렬된 배열의 중앙값
8. 배열에서 K번째로 큰 요소
9. 가장 가까운 K개 요소 찾기
10. 크기를 알 수 없는 정렬된 배열에서 검색
11. D일 이내에 패키지 배송 가능
12. 바나나를 먹는 코코
13. 중복번호 찾기
14. 최대 K개의 고유 문자를 포함하는 가장 긴 부분 문자열
15. 하위 배열의 합은 K와 같습니다

이러한 문제는 광범위한 배열 검색 기술을 다루며 이 블로그 게시물에서 논의된 개념을 더욱 확실하게 이해하는 데 도움이 됩니다.

결론적으로, 데이터 구조와 알고리즘에 능숙해지려면 배열 검색 기술을 익히는 것이 중요합니다. 이러한 다양한 방법을 이해하고 구현함으로써 복잡한 문제를 해결하고 코드를 최적화하는 데 더 나은 준비를 갖추게 됩니다. 각 접근 방식의 시간 및 공간 복잡성을 분석하고 문제의 특정 요구 사항에 따라 가장 적합한 접근 방식을 선택하는 것을 잊지 마세요.

즐거운 코딩과 검색을 즐겨보세요!

以上がJavaScript を使用した DSA での配列検索: 基本から高度までの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。