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.

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. 2つの合計
2. 回転ソート配列で検索
3. 回転ソートされた配列の最小値を見つける
4. 2D マトリックスを検索
5. ピーク要素の検索
6. 範囲を検索
7. ソートされた 2 つの配列の中央値
8. 配列内の K 番目に大きい要素
9. K 個の最も近い要素を検索
10. サイズが不明なソートされた配列を検索
11. D 日以内に荷物を発送できる能力
12. バナナを食べるココ
13. 重複する番号を見つける
14. 最大 K 個の異なる文字を含む最長の部分文字列
15. サブ配列の合計は 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!