Pencarian tatasusunan ialah konsep asas dalam Struktur Data dan Algoritma (DSA). Catatan blog ini akan merangkumi pelbagai teknik carian tatasusunan menggunakan JavaScript, dari peringkat asas hingga lanjutan. Kami akan meneroka 20 contoh, membincangkan kerumitan masa dan menyediakan masalah LeetCode untuk latihan.
Carian linear ialah algoritma carian paling mudah yang berfungsi pada tatasusunan yang diisih dan tidak diisih.
Kerumitan Masa: O(n), dengan n ialah bilangan elemen dalam tatasusunan.
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
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]
Carian binari ialah algoritma yang cekap untuk mencari dalam tatasusunan yang diisih.
Kerumitan Masa: O(log n)
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
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
Carian lompat ialah algoritma untuk tatasusunan diisih yang berfungsi dengan melangkau beberapa elemen untuk mengurangkan bilangan perbandingan.
Kerumitan Masa: O(√n)
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
Carian interpolasi ialah varian carian binari yang dipertingkatkan untuk tatasusunan diisih yang diedarkan secara seragam.
Kerumitan Masa: O(log log n) untuk data teragih seragam, O(n) dalam kes yang paling teruk.
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
Carian eksponen berguna untuk carian tanpa sempadan dan berfungsi dengan baik untuk tatasusunan terhad juga.
Kerumitan Masa: O(log n)
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
Mencari subarray dalam tatasusunan yang lebih besar ialah masalah biasa dalam DSA.
Kerumitan Masa: O(n * m), dengan n ialah panjang tatasusunan utama dan m ialah panjang 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
Kerumitan Masa: 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
Teknik dua mata sering digunakan untuk mencari dalam tatasusunan yang disusun atau apabila berurusan dengan pasangan.
Kerumitan Masa: 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]
Kerumitan Masa: 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]]
Teknik tetingkap gelongsor berguna untuk menyelesaikan masalah tatasusunan/rentetan dengan elemen bersebelahan.
Kerumitan Masa: 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
Kerumitan Masa: 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
Kerumitan Masa: 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
Kerumitan Masa: O(log(m * n)), dengan m ialah bilangan baris dan n ialah bilangan lajur
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
Kerumitan Masa: 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
Kerumitan Masa: 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
Kerumitan Masa: 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
Kerumitan Masa: 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]
Kerumitan Masa: O(log(min(m, n))), dengan m dan n ialah panjang dua tatasusunan
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
Untuk menguji lagi pemahaman dan kemahiran anda dalam pencarian tatasusunan, berikut ialah 15 masalah LeetCode yang boleh anda amalkan:
Ces problèmes couvrent un large éventail de techniques de recherche de tableaux et vous aideront à consolider votre compréhension des concepts abordés dans cet article de blog.
En conclusion, maîtriser les techniques de recherche de tableaux est crucial pour maîtriser les structures de données et les algorithmes. En comprenant et en mettant en œuvre ces différentes méthodes, vous serez mieux équipé pour résoudre des problèmes complexes et optimiser votre code. N'oubliez pas d'analyser la complexité temporelle et spatiale de chaque approche et de choisir la plus appropriée en fonction des exigences spécifiques de votre problématique.
Bon codage et bonne recherche !
Atas ialah kandungan terperinci Carian Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Ciri-ciri rangkaian
Bagaimana untuk mengekalkan bilangan tempat perpuluhan dalam C++
Bagaimana untuk menyediakan muat semula automatik halaman web
Bagaimana untuk menyelesaikan sintaks yang tidak sah dalam Python
Bagaimana untuk menjadi kawan rapat di TikTok
freelaunchbar
pelayan web
Berapakah nilai Dimensity 9000 bersamaan dengan Snapdragon?
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
