지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 웹 프론트엔드 > JS 튜토리얼 > JavaScript를 사용한 DSA의 배열 검색: 기초부터 고급까지

JavaScript를 사용한 DSA의 배열 검색: 기초부터 고급까지

WBOY
풀어 주다： 2024-09-04 22:47:32
원래의
605명이 탐색했습니다.

Array Searching in DSA using JavaScript: From Basics to Advanced

배열 검색은 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. 두 포인터 기법

두 포인터 기법은 정렬된 배열을 검색하거나 쌍을 처리할 때 자주 사용됩니다.

예제 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: 두 개의 정렬된 배열의 중앙값

시간 복잡도: O(log(min(m, n))), 여기서 m과 n은 두 배열의 길이입니다

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. Dua Jumlah
  2. Cari dalam Tatasusunan Isih Diputar
  3. Cari Minimum dalam Tatasusunan Isih Diputar
  4. Cari Matriks 2D
  5. Cari Elemen Puncak
  6. Cari Julat
  7. Median Dua Tatasusunan Isih
  8. Kth Elemen Terbesar dalam Tatasusunan
  9. Cari K Elemen Terdekat
  10. Cari dalam Susunan Isih Saiz Tidak Diketahui
  11. Kapasiti Menghantar Pakej Dalam D Hari
  12. Koko Makan Pisang
  13. Cari Nombor Pendua
  14. Subrentetan Terpanjang dengan Paling Banyak Aksara K Distinct
  15. Jumlah Subarray Sama dengan K

Masalah ini merangkumi pelbagai teknik pencarian tatasusunan dan akan membantu anda mengukuhkan pemahaman anda tentang konsep yang dibincangkan dalam catatan blog ini.

Kesimpulannya, menguasai teknik pencarian tatasusunan adalah penting untuk menjadi mahir dalam Struktur Data dan Algoritma. Dengan memahami dan melaksanakan pelbagai kaedah ini, anda akan lebih bersedia untuk menangani masalah yang rumit dan mengoptimumkan kod anda. Ingat untuk menganalisis kerumitan masa dan ruang bagi setiap pendekatan dan pilih yang paling sesuai berdasarkan keperluan khusus masalah anda.

Selamat mengekod dan mencari!

위 내용은 JavaScript를 사용한 DSA의 배열 검색: 기초부터 고급까지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천：dev.to
이전 기사：모의 요청 다음 기사：프런트엔드 개발자를 위한 최고의 JavaScript 프레임워크
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
function_exists()는 사용자 정의 함수를 결정할 수 없습니다. 기능 테스트() {                                                                                ...
에서 2024-04-29 11:01:01
0
3
2250
Chrome 모바일 버전을 표시하는 방법 안녕하세요 선생님, Chrome을 모바일 버전으로 어떻게 변경하나요?
에서 2024-04-23 00:22:19
0
11
2387
자식 창이 부모 창을 작동하지만 출력이 응답하지 않습니다. 처음 두 문장은 실행 가능하지만 마지막 문장은 구현할 수 없습니다.
에서 2024-04-19 15:37:47
0
1
1998
상위 창에 출력이 없습니다. document.onclick = function(){ window.opener.document.write('나는 자식 창의 출력입니다.');
에서 2024-04-18 23:52:34
0
1
1885
CSS 마인드맵 코스웨어는 어디에 있나요? 코스웨어
에서 2024-04-16 10:10:18
0
0
1954
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿