Array Searching in DSA using JavaScript: From Basics to Advanced-JS Tutorial-php.cn

Array Searching in DSA using JavaScript: From Basics to Advanced

Array searching is a fundamental concept in Data Structures and Algorithms (DSA). This blog post will cover various array searching techniques using JavaScript, ranging from basic to advanced levels. We'll explore 20 examples, discuss time complexities, and provide LeetCode problems for practice.

Linear Search
Binary Search
Jump Search
Interpolation Search
Exponential Search
Subarray Search
Two Pointer Technique
Sliding Window Technique
Advanced Searching Techniques
LeetCode Practice Problems

1. Linear Search

Linear search is the simplest searching algorithm that works on both sorted and unsorted arrays.

Time Complexity: O(n), where n is the number of elements in the array.

Example 1: Basic Linear Search

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

Copy after login

Example 2: Find All Occurrences

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]

Copy after login

2. Binary Search

Binary search is an efficient algorithm for searching in sorted arrays.

Time Complexity: O(log n)

Example 3: Iterative Binary Search

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

Copy after login

Example 4: Recursive Binary Search

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

Copy after login

3. Jump Search

Jump search is an algorithm for sorted arrays that works by skipping some elements to reduce the number of comparisons.

Time Complexity: O(√n)

Example 5: Jump Search Implementation

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

Copy after login

4. Interpolation Search

Interpolation search is an improved variant of binary search for uniformly distributed sorted arrays.

Time Complexity: O(log log n) for uniformly distributed data, O(n) in the worst case.

Example 6: Interpolation Search Implementation

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

Copy after login

5. Exponential Search

Exponential search is useful for unbounded searches and works well for bounded arrays too.

Time Complexity: O(log n)

Example 7: Exponential Search Implementation

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

Copy after login

6. Subarray Search

Searching for subarrays within a larger array is a common problem in DSA.

Example 8: Naive Subarray Search

Time Complexity: O(n * m), where n is the length of the main array and m is the length of the subarray.

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

Copy after login

Example 9: KMP Algorithm for Subarray Search

Time Complexity: 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

Copy after login

7. Two Pointer Technique

The two-pointer technique is often used for searching in sorted arrays or when dealing with pairs.

Example 10: Find Pair with Given Sum

Time Complexity: 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]

Copy after login

Example 11: Three Sum Problem

Time Complexity: 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]]

Copy after login

8. Sliding Window Technique

The sliding window technique is useful for solving array/string problems with contiguous elements.

Example 12: Maximum Sum Subarray of Size K

Time Complexity: 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

Copy after login

Example 13: Longest Substring with K Distinct Characters

Time Complexity: 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

Copy after login

9. Advanced Searching Techniques

Example 14: Search in Rotated Sorted Array

Time Complexity: 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

Copy after login

Example 15: Search in a 2D Matrix

Time Complexity: O(log(m * n)), where m is the number of rows and n is the number of columns

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

Copy after login

Example 16: Find Peak Element

Time Complexity: 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

Copy after login

Example 17: Search in Sorted Array of Unknown Size

Time Complexity: 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

Copy after login

Example 18: Find Minimum in Rotated Sorted Array

Time Complexity: 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

Copy after login

Example 19: Search for a Range

Time Complexity: 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]

Copy after login

Example 20: Median of Two Sorted Arrays

Time Complexity: O(log(min(m, n))), where m and n are the lengths of the two arrays

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

Copy after login

10. LeetCode Practice Problems

To further test your understanding and skills in array searching, here are 15 LeetCode problems you can practice:

2つの合計
回転ソート配列で検索
回転ソートされた配列の最小値を見つける
2D マトリックスを検索
ピーク要素の検索
範囲を検索
ソートされた 2 つの配列の中央値
配列内の K 番目に大きい要素
K 個の最も近い要素を検索
サイズが不明なソートされた配列を検索
D 日以内に荷物を発送できる能力
バナナを食べるココ
重複する番号を見つける
最大 K 個の異なる文字を含む最長の部分文字列
サブ配列の合計は K に等しい

これらの問題は、広範囲の配列検索テクニックをカバーしており、このブログ投稿で説明されている概念の理解を確実にするのに役立ちます。

結論として、データ構造とアルゴリズムに習熟するには、配列検索テクニックを習得することが重要です。これらのさまざまな方法を理解して実装することで、複雑な問題に取り組み、コードを最適化する準備が整います。各アプローチの時間と空間の複雑さを分析し、問題の特定の要件に基づいて最も適切なものを選択することを忘れないでください。

コーディングと検索を楽しんでください!

The above is the detailed content of Array Searching in DSA using JavaScript: From Basics to Advanced. For more information, please follow other related articles on the PHP Chinese website!