Array-Suche in DSA mit JavaScript: Von den Grundlagen bis zu Fortgeschrittenen

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.

Table of Contents

1. Linear Search
2. Binary Search
3. Jump Search
4. Interpolation Search
5. Exponential Search
6. Subarray Search
7. Two Pointer Technique
8. Sliding Window Technique
9. Advanced Searching Techniques
10. 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

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]

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

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

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

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

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

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

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

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]

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]]

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

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

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

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

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

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

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

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]

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

10. LeetCode Practice Problems

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

1. Two Sum
2. Search in Rotated Sorted Array
3. Find Minimum in Rotated Sorted Array
4. Search a 2D Matrix
5. Find Peak Element
6. Search for a Range
7. Median of Two Sorted Arrays
8. Kth Largest Element in an Array
9. Find K Closest Elements
10. Search in a Sorted Array of Unknown Size
11. Capacity To Ship Packages Within D Days
12. Koko Eating Bananas
13. Find the Duplicate Number
14. Longest Substring with At Most K Distinct Characters
15. Subarray Sum Equals K

These problems cover a wide range of array searching techniques and will help you solidify your understanding of the concepts discussed in this blog post.

In conclusion, mastering array searching techniques is crucial for becoming proficient in Data Structures and Algorithms. By understanding and implementing these various methods, you'll be better equipped to tackle complex problems and optimize your code. Remember to analyze the time and space complexity of each approach and choose the most appropriate one based on the specific requirements of your problem.

Happy coding and searching!

Das obige ist der detaillierte Inhalt vonArray-Suche in DSA mit JavaScript: Von den Grundlagen bis zu Fortgeschrittenen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!