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 



<h3>
  
  
  Example 2: Find All Occurrences
</h3>



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



<h2>
  
  
  2. Binary Search
</h2>

<p>Binary search is an efficient algorithm for searching in sorted arrays.</p>

<p><strong>Time Complexity:</strong> O(log n)</p>

<h3>
  
  
  Example 3: Iterative Binary Search
</h3>



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

    while (left 



<h3>
  
  
  Example 4: Recursive Binary Search
</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. Jump Search
</h2>

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

<p><strong>Time Complexity:</strong> O(√n)</p>

<h3>
  
  
  Example 5: Jump Search Implementation
</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. Interpolation Search
</h2>

<p>Interpolation search is an improved variant of binary search for uniformly distributed sorted arrays.</p>

<p><strong>Time Complexity:</strong> O(log log n) for uniformly distributed data, O(n) in the worst case.</p>

<h3>
  
  
  Example 6: Interpolation Search Implementation
</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. Exponential Search
</h2>

<p>Exponential search is useful for unbounded searches and works well for bounded arrays too.</p>

<p><strong>Time Complexity:</strong> O(log n)</p>

<h3>
  
  
  Example 7: Exponential Search Implementation
</h3>



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

    let i = 1;
    while (i 



<h2>
  
  
  6. Subarray Search
</h2>

<p>Searching for subarrays within a larger array is a common problem in DSA.</p>

<h3>
  
  
  Example 8: Naive Subarray Search
</h3>

<p><strong>Time Complexity:</strong> O(n * m), where n is the length of the main array and m is the length of the subarray.<br>
</p>

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



<h3>
  
  
  Example 9: KMP Algorithm for Subarray Search
</h3>

<p><strong>Time Complexity:</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. Two Pointer Technique
</h2>

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

<h3>
  
  
  Example 10: Find Pair with Given Sum
</h3>

<p><strong>Time Complexity:</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>
  
  
  Example 11: Three Sum Problem
</h3>

<p><strong>Time Complexity:</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. Sliding Window Technique
</h2>

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

<h3>
  
  
  Example 12: Maximum Sum Subarray of Size K
</h3>

<p><strong>Time Complexity:</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>
  
  
  Example 13: Longest Substring with K Distinct Characters
</h3>

<p><strong>Time Complexity:</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. 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 = arr[left] && target  arr[mid] && target 



<h3>
  
  
  Example 15: Search in a 2D Matrix
</h3>

<p><strong>Time Complexity:</strong> O(log(m * n)), where m is the number of rows and n is the number of columns<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>
  
  
  Example 16: Find Peak Element
</h3>

<p><strong>Time Complexity:</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

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] 



<h3>
  
  
  Example 18: Find Minimum in Rotated Sorted Array
</h3>

<p><strong>Time Complexity:</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

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 



<h3>
  
  
  Example 20: Median of Two Sorted Arrays
</h3>

<p><strong>Time Complexity:</strong> O(log(min(m, n))), where m and n are the lengths of the two arrays<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. 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!