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
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Subarray Search
- Two Pointer Technique
- Sliding Window Technique
- Advanced Searching Techniques
- 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 < 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
Example 2: Find All Occurrences
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. Binary Search
Binary search is an efficient algorithm for searching in sorted arrays.
Time Complexity: O(log n)
Example 3: Iterative Binary Search
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
Example 4: Recursive Binary Search
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. Jump Search
Jump search is an algorithm for sorted arrays that works by skipping some elements to reduce the number of comparisons.
Time Complexity: O(√n)
Example 5: Jump Search Implementation
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. Interpolation Search
Interpolation search is an improved variant of binary search for uniformly distributed sorted arrays.
Time Complexity: O(log log n) for uniformly distributed data, O(n) in the worst case.
Example 6: Interpolation Search Implementation
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. Exponential Search
Exponential search is useful for unbounded searches and works well for bounded arrays too.
Time Complexity: O(log n)
Example 7: Exponential Search Implementation
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. Subarray Search
Searching for subarrays within a larger array is a common problem in DSA.
Example 8: Naive Subarray Search
Time Complexity: O(n * m), where n is the length of the main array and m is the length of the 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
Example 9: KMP Algorithm for Subarray Search
Time Complexity: 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. Two Pointer Technique
The two-pointer technique is often used for searching in sorted arrays or when dealing with pairs.
Example 10: Find Pair with Given Sum
Time Complexity: 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]
Example 11: Three Sum Problem
Time Complexity: 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. Sliding Window Technique
The sliding window technique is useful for solving array/string problems with contiguous elements.
Example 12: Maximum Sum Subarray of Size K
Time Complexity: 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
Example 13: Longest Substring with K Distinct Characters
Time Complexity: 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. 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 <= 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
Example 15: Search in a 2D Matrix
Time Complexity: O(log(m * n)), where m is the number of rows and n is the number of columns
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
Example 16: Find Peak Element
Time Complexity: 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
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] < 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
Example 18: Find Minimum in Rotated Sorted Array
Time Complexity: 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
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 <= 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]
Example 20: Median of Two Sorted Arrays
Time Complexity: O(log(min(m, n))), where m and n are the lengths of the two arrays
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 Practice Problems
To further test your understanding and skills in array searching, here are 15 LeetCode problems you can practice:
- Two Sum
- Search in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array
- Search a 2D Matrix
- Find Peak Element
- Search for a Range
- Median of Two Sorted Arrays
- Kth Largest Element in an Array
- Find K Closest Elements
- Search in a Sorted Array of Unknown Size
- Capacity To Ship Packages Within D Days
- Koko Eating Bananas
- Find the Duplicate Number
- Longest Substring with At Most K Distinct Characters
- 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!
Top comments (0)