🔍 JS Searching
Index: Searching Index | Parent: JS Array Index
1. Built-in Search Methods
// indexOf — find value's index (uses ===)
[1,2,3,2,1].indexOf(2); // 1 (first)
[1,2,3,2,1].lastIndexOf(2); // 3 (last)
[1,2,3].indexOf(9); // -1 (not found)
// includes — boolean check (handles NaN)
[1,2,NaN].includes(NaN); // true
[1,2,3].includes(2); // true
// find — first element matching condition
[5,12,8,130].find(x => x > 10); // 12
[{id:1},{id:2}].find(o => o.id === 2); // {id:2}
// findIndex — index of first match
[5,12,8,130].findIndex(x => x > 10); // 1
// findLast / findLastIndex (ES2023)
[1,2,3,4,3].findLast(x => x === 3); // 3 (at index 4)
[1,2,3,4,3].findLastIndex(x => x===3);// 42. Linear Search O(n)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// When to use:
// - Unsorted array
// - Small array
// - Searching by complex condition (use find())3. Binary Search O(log n)
Prerequisite: Array must be sorted.
// Iterative Binary Search
function binarySearch(arr, target) {
let left = 0, 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;
}
// Recursive Binary Search
function binarySearchRecursive(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;
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid+1, right);
return binarySearchRecursive(arr, target, left, mid-1);
}
console.log(binarySearch([1,3,5,7,9,11], 7)); // 3
console.log(binarySearch([1,3,5,7,9,11], 6)); // -14. Binary Search Variants
First Occurrence
function firstOccurrence(arr, target) {
let left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1; // keep searching LEFT
} else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}Last Occurrence
function lastOccurrence(arr, target) {
let left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
left = mid + 1; // keep searching RIGHT
} else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}Search in Rotated Sorted Array [M][FB]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Binary search on array that was sorted but then rotated. Key signal: "rotated sorted array".
Step 2 — Brute force:
Linear scan → O(n). We need O(log n) — must binary search.
Step 3 — Key insight:
Even in a rotated array, ONE of the two halves is always fully sorted. Check which half is sorted, then determine if target lies within that sorted half. Recurse on the side that can contain the target.
Step 4 — Algorithm:
1. left=0, right=n-1
2. If nums[left] <= nums[mid]: left half is sorted
- If left <= target < mid: search left, else search right
3. Else: right half is sorted
- If mid < target <= right: search right, else search left
Step 5 — Edge cases:
- Single element: check if it equals target
- No rotation: works exactly like standard binary search
function searchRotated(nums, target) { let left = 0, right = nums.length - 1;
while (left <= right) { const mid = Math.floor((left + right) / 2); if (nums[mid] === target) return mid;
// Left half is sorted if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { // Right half is sorted if (nums[mid] < target && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; }
console.log(searchRotated([4,5,6,7,0,1,2], 0)); // 4 console.log(searchRotated([4,5,6,7,0,1,2], 3)); // -1
### Find Peak Element `[M]`
> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> Find any peak (not necessarily the max) + O(log n) = Binary Search based on slope direction.
>
> **Step 2 — Brute force:**
> Linear scan, check if nums[i] > both neighbors → O(n).
>
> **Step 3 — Key insight:**
> If nums[mid] < nums[mid+1], then the slope is going UP to the right — a peak must exist in the right half (could be nums[mid+1] itself or further right). If nums[mid] > nums[mid+1], slope goes DOWN — peak is in left half including mid.
>
> **Step 4 — Algorithm:**
> 1. left=0, right=n-1
> 2. While left < right: mid = (left+right)/2
> 3. If nums[mid] > nums[mid+1]: right = mid (peak is here or left)
> 4. Else: left = mid+1 (peak is to the right)
> 5. Return left
>
> **Step 5 — Edge cases:**
> - Single element: it's the peak
> - Monotonically increasing: peak is last element
function findPeakElement(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
console.log(findPeakElement([1,2,3,1])); // 2 (value 3)
console.log(findPeakElement([1,2,1,3,5,6,4])); // 5 (value 6)Binary Search on Answer — Koko Eating Bananas [M]
// Find minimum eating speed k such that Koko finishes in h hours
function minEatingSpeed(piles, h) {
let left = 1, right = Math.max(...piles);
while (left < right) {
const mid = Math.floor((left + right) / 2);
const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
if (hours <= h) right = mid;
else left = mid + 1;
}
return left;
}
console.log(minEatingSpeed([3,6,7,11], 8)); // 45. Search in 2D Matrix [M][FB]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Sorted matrix where rows increase left-to-right and columns increase top-to-bottom. Start from a corner that gives binary choice each step.
Step 2 — Brute force:
Check every cell → O(n×m). Need O(n+m).
Step 3 — Key insight:
Top-right corner is the "binary search sweet spot": it's the largest in its row (so go left if too big) and smallest in its column (so go down if too small). Each comparison eliminates a full row or column.
Step 4 — Algorithm:
1. row=0, col=lastCol
2. While in bounds: if match → true; if too big → col--; if too small → row++
Step 5 — Edge cases:
- Target smaller than top-left: col goes to -1, exits
- Target larger than bottom-right: row goes past last row, exits
Way of Thinking: Start at top-right corner. If value = target → found. If value > target → go left. If value < target → go down.
function searchMatrix(matrix, target) {
let row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}
const matrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
];
console.log(searchMatrix(matrix, 5)); // true
console.log(searchMatrix(matrix, 20)); // false