JavaScript を使用した DSA での配列検索: 基本から高度まで
配列検索は、データ構造とアルゴリズム (DSA) の基本概念です。このブログ投稿では、基本レベルから高度なレベルまで、JavaScript を使用したさまざまな配列検索テクニックを取り上げます。 20 の例を検討し、時間計算量について説明し、練習用に LeetCode の問題を提供します。
目次
- 線形検索
- 二分探索
- ジャンプ検索
- 補間検索
- 指数関数的検索
- サブ配列検索
- ツーポインターテクニック
- スライディングウィンドウテクニック
- 高度な検索テクニック
- 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. ツーポインターテクニック
2 ポインター手法は、ソートされた配列内の検索やペアを扱う場合によく使用されます。
例 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: ソートされた 2 つの配列の中央値
時間計算量: O(log(min(m, n)))、ここで、m と n は 2 つの配列の長さです
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 の問題を次に示します。
- 투썸
- 회전 정렬 배열에서 검색
- 회전 정렬 배열에서 최소값 찾기
- 2D 매트릭스 검색
- 피크 요소 찾기
- 범위 검색
- 두 개의 정렬된 배열의 중앙값
- 배열에서 K번째로 큰 요소
- 가장 가까운 K개 요소 찾기
- 크기를 알 수 없는 정렬된 배열에서 검색
- D일 이내에 패키지 배송 가능
- 바나나를 먹는 코코
- 중복번호 찾기
- 최대 K개의 고유 문자를 포함하는 가장 긴 부분 문자열
- 하위 배열의 합은 K와 같습니다
이러한 문제는 광범위한 배열 검색 기술을 다루며 이 블로그 게시물에서 논의된 개념을 더욱 확실하게 이해하는 데 도움이 됩니다.
결론적으로, 데이터 구조와 알고리즘에 능숙해지려면 배열 검색 기술을 익히는 것이 중요합니다. 이러한 다양한 방법을 이해하고 구현함으로써 복잡한 문제를 해결하고 코드를 최적화하는 데 더 나은 준비를 갖추게 됩니다. 각 접근 방식의 시간 및 공간 복잡성을 분석하고 문제의 특정 요구 사항에 따라 가장 적합한 접근 방식을 선택하는 것을 잊지 마세요.
즐거운 코딩과 검색을 즐겨보세요!
以上がJavaScript を使用した DSA での配列検索: 基本から高度までの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
1670
14
1428
52
1329
25
1274
29
1256
24
Python vs. JavaScript：学習曲線と使いやすさ
Apr 16, 2025 am 12:12 AM
Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。
C/CからJavaScriptへ：すべてがどのように機能するか
Apr 14, 2025 am 12:05 AM
C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1）C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2）C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3）JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。
JavaScriptとWeb：コア機能とユースケース
Apr 18, 2025 am 12:19 AM
Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1）DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2）ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3）サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。
JavaScript in Action：実際の例とプロジェクト
Apr 19, 2025 am 12:13 AM
現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1）DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2）node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。
JavaScriptエンジンの理解：実装の詳細
Apr 17, 2025 am 12:05 AM
JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1）エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2）実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3）ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。
Python vs. JavaScript：コミュニティ、ライブラリ、リソース
Apr 15, 2025 am 12:16 AM
PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1）Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2）Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3）どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。
Python vs. JavaScript：開発環境とツール
Apr 26, 2025 am 12:09 AM
開発環境におけるPythonとJavaScriptの両方の選択が重要です。 1）Pythonの開発環境には、Pycharm、Jupyternotebook、Anacondaが含まれます。これらは、データサイエンスと迅速なプロトタイピングに適しています。 2）JavaScriptの開発環境には、フロントエンドおよびバックエンド開発に適したnode.js、vscode、およびwebpackが含まれます。プロジェクトのニーズに応じて適切なツールを選択すると、開発効率とプロジェクトの成功率が向上する可能性があります。
JavaScript通訳者とコンパイラにおけるC/Cの役割
Apr 20, 2025 am 12:01 AM
CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1）cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2）Cは、Bytecodeの生成と実行を担当します。 3）Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。
