Linear Search checks each element sequentially until the target is found or the array ends. Works on unsorted arrays.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// linearSearch([5, 3, 8, 1], 8) => 2
Time: O(n) | Space: O(1)
Binary Search works on sorted arrays by repeatedly dividing the search range in half. Compare the target with the middle element and eliminate half the array each step.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
Time: O(log n) | Space: O(1)
Binary Search on the answer applies binary search not on an array, but on the range of possible answers. You define a condition and binary search for the boundary where it changes.
// Example: find minimum capacity to ship packages in D days
function shipWithinDays(weights, days) {
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (canShip(weights, days, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
This pattern is used when the answer space is monotonic (sorted by feasibility).
A rotated sorted array has two sorted halves. Use modified binary search: determine which half is sorted, then check if the target lies in that half.
function searchRotated(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[lo] <= arr[mid]) { // left half sorted
if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half sorted
if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
Time: O(log n) | Space: O(1)
A peak element is greater than or equal to its neighbors. Use binary search: if the mid element is less than its right neighbor, a peak exists on the right side, and vice versa.
function findPeak(arr) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < arr[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo; // index of peak
}
// findPeak([1, 3, 20, 4, 1]) => 2
Time: O(log n) | Space: O(1)
Use two binary searches: one biased left to find the first occurrence and one biased right for the last.
function findFirst(arr, target) {
let lo = 0, hi = arr.length - 1, res = -1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) { res = mid; hi = mid - 1; }
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
function findLast(arr, target) {
let lo = 0, hi = arr.length - 1, res = -1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) { res = mid; lo = mid + 1; }
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
Time: O(log n) each | Space: O(1)
Binary search for the largest integer whose square is ≤ the target number. Search the range [0, n].
function sqrt(n) {
let lo = 0, hi = n, ans = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid <= n) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
// sqrt(26) => 5 (5*5=25 <= 26)
Time: O(log n) | Space: O(1)
If each row is sorted and the first element of each row is greater than the last of the previous row, treat the 2D matrix as a flattened sorted array and apply binary search.
function searchMatrix(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let lo = 0, hi = m * n - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
const val = matrix[Math.floor(mid / n)][mid % n];
if (val === target) return true;
else if (val < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
Time: O(log(m · n)) | Space: O(1)
Ternary Search divides the search space into three parts instead of two. It is useful for finding the maximum or minimum of a unimodal function.
function ternarySearch(f, lo, hi) {
while (hi - lo > 1e-9) {
const m1 = lo + (hi - lo) / 3;
const m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) lo = m1;
else hi = m2;
}
return (lo + hi) / 2;
}
// Finds x where f(x) is maximized in [lo, hi]
Time: O(log n) | Slightly slower than binary search in practice due to more comparisons per step.
Interpolation Search improves on binary search for uniformly distributed data by estimating the position using the value of the target relative to the range.
function interpolationSearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
const pos = lo + Math.floor(
((target - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo])
);
if (arr[pos] === target) return pos;
if (arr[pos] < target) lo = pos + 1;
else hi = pos - 1;
}
return -1;
}
Time: O(log log n) average for uniform data, O(n) worst case | Space: O(1)
Start from the top-right corner. If current > target, move left. If current < target, move down. One step eliminates a full row or column.
function searchMatrix2D(matrix, target) {
let r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] === target) return true;
else if (matrix[r][c] > target) c--; // trim column
else r++; // trim row
}
return false;
}
// Input: [[1,4,7],[2,5,8],[3,6,9]], target=5 => Output: true
// Input: [[1,4,7],[2,5,8],[3,6,9]], target=4 => Output: true
// Input: [[1,4],[2,5]], target=3 => Output: false
Time: O(m + n) — at most m+n steps | Space: O(1)
A peak is an element greater than its neighbors. Use binary search: if mid < mid+1, the peak is to the right; otherwise it's to the left (or is mid itself).
function findPeakElement(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] < nums[mid + 1]) lo = mid + 1; // upslope → peak right
else hi = mid; // downslope → peak here or left
}
return lo;
}
// Input: [1,2,3,1] => Output: 2 (index of peak 3)
// Input: [1,2,1,3,5,6,4] => Output: 5 (index of 6)
// Input: [1] => Output: 0
Time: O(log n) | Space: O(1)
Run two binary searches: one to find the leftmost occurrence (lower_bound) and one for the rightmost (upper_bound - 1).
function searchRange(nums, target) {
function lowerBound() {
let lo = 0, hi = nums.length - 1, result = -1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) { result = mid; hi = mid - 1; } // keep searching left
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return result;
}
function upperBound() {
let lo = 0, hi = nums.length - 1, result = -1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) { result = mid; lo = mid + 1; } // keep searching right
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return result;
}
return [lowerBound(), upperBound()];
}
// Input: nums=[5,7,7,8,8,10], target=8 => Output: [3,4]
// Input: nums=[5,7,7,8,8,10], target=6 => Output: [-1,-1]
Time: O(log n) | Space: O(1)
Extend the no-duplicates approach: when mid == left, increment left to handle the ambiguous case where you can't determine which side is sorted.
function searchInRotatedWithDups(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) return true;
// Handle duplicates: can't determine which side is sorted
if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) {
lo++; hi--;
} else if (nums[lo] <= nums[mid]) { // left half sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
// Input: nums=[2,5,6,0,0,1,2], target=0 => Output: true
// Input: nums=[2,5,6,0,0,1,2], target=3 => Output: false
Time: O(log n) average, O(n) worst with many duplicates | Space: O(1)
Binary search in the range [0, x]. Find the largest integer m where m² ≤ x. Avoid overflow by using BigInt or checking m ≤ x/m instead of m*m.
function mySqrt(x) {
if (x < 2) return x;
let lo = 1, hi = Math.floor(x / 2); // sqrt(x) <= x/2 for x >= 4
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid === x) return mid;
else if (mid * mid < x) lo = mid + 1;
else hi = mid - 1;
}
return hi; // floor of sqrt
}
// Input: 4 => Output: 2
// Input: 8 => Output: 2 (floor of 2.828...)
// Input: 100 => Output: 10
Time: O(log x) | Space: O(1)
Binary search: the minimum is in the unsorted half. Compare mid with hi to determine which half is sorted and where the rotation point (minimum) is.
function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] > nums[hi]) lo = mid + 1; // min is in right half
else hi = mid; // min is at mid or left
}
return nums[lo];
}
// Input: [3,4,5,1,2] => Output: 1
// Input: [4,5,6,7,0,1,2] => Output: 0
// Input: [1] => Output: 1
Time: O(log n) | Space: O(1)
When you need to find the minimum/maximum value satisfying a condition, binary search on the answer space. Define a canAchieve(mid) predicate and narrow the search.
// Example: Koko eating bananas — minimum eating speed to finish in h hours
function minEatingSpeed(piles, h) {
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
if (hours <= h) hi = mid; // can eat slower
else lo = mid + 1; // need to eat faster
}
return lo;
}
// Input: piles=[3,6,7,11], h=8 => Output: 4 (speed 4 bananas/hr)
// Input: piles=[30,11,23,4,20], h=5 => Output: 30
Time: O(n log m) where m = max pile | Space: O(1)
Find the first (lower bound) and last (upper bound) positions of the target using two binary searches. Count = last - first + 1.
function countOccurrences(nums, target) {
function lowerBound(nums, target) {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] < target) lo = mid + 1; else hi = mid;
}
return lo;
}
const first = lowerBound(nums, target);
const last = lowerBound(nums, target + 1);
return last - first;
}
// Input: [1,2,2,2,3,4], target=2 => Output: 3
// Input: [1,3,5,7,9], target=4 => Output: 0
// Input: [2,2,2,2], target=2 => Output: 4
Time: O(log n) | Space: O(1)
Maintain a sorted array (or BST) with binary search for insertion position using bisect-like logic. The kth element is at index k-1.
class OrderStatistics {
constructor() { this.sorted = []; }
insert(val) {
// Binary search for insertion point
let lo = 0, hi = this.sorted.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (this.sorted[mid] < val) lo = mid + 1; else hi = mid;
}
this.sorted.splice(lo, 0, val);
}
kthSmallest(k) {
return this.sorted[k - 1];
}
}
const os = new OrderStatistics();
os.insert(5); os.insert(2); os.insert(8); os.insert(1);
os.kthSmallest(2); // => 2 (sorted: [1,2,5,8])
os.kthSmallest(3); // => 5
Insert Time: O(n) — splice is O(n) | Query: O(1)
Exponential Search first finds a range [2^i, 2^(i+1)) where the target exists (by doubling), then applies binary search within that range. Useful when the array is unbounded.
function exponentialSearch(arr, target) {
if (arr[0] === target) return 0;
// Find range: double i until arr[i] >= target
let i = 1;
while (i < arr.length && arr[i] <= target) i *= 2;
// Binary search in [i/2, min(i, arr.length-1)]
let lo = Math.floor(i / 2), hi = Math.min(i, arr.length - 1);
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Input: [1,2,3,4,5,6,7,8,9,10], target=7 => Output: 6 (index)
// Input: [1,10,100,1000], target=100 => Output: 2
Time: O(log n) | Space: O(1)
When the answer is a real number, binary search with a precision threshold (epsilon). Iterate until hi - lo < eps.
// Example: find cube root of a number
function cubeRoot(n) {
let lo = 0, hi = Math.max(1, n);
const eps = 1e-9;
while (hi - lo > eps) {
const mid = (lo + hi) / 2;
if (mid * mid * mid < n) lo = mid;
else hi = mid;
}
return (lo + hi) / 2;
}
// Input: 27 => Output: 3.0
// Input: 8 => Output: 2.0
// Input: 0.5 => Output: ~0.7937
// Another example: find x such that f(x) = target
// Binary search works on any monotone function f
Time: O(log((hi-lo)/eps)) iterations | Space: O(1)
Binary search on the partition point of the shorter array. Partition both arrays such that left halves combined have (m+n)/2 elements. Check if the partition is correct.
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length, n = nums2.length;
let lo = 0, hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2); // partition in nums1
const j = Math.floor((m + n + 1) / 2) - i; // partition in nums2
const maxL1 = i === 0 ? -Infinity : nums1[i-1];
const minR1 = i === m ? Infinity : nums1[i];
const maxL2 = j === 0 ? -Infinity : nums2[j-1];
const minR2 = j === n ? Infinity : nums2[j];
if (maxL1 <= minR2 && maxL2 <= minR1) {
if ((m + n) % 2 === 1) return Math.max(maxL1, maxL2);
return (Math.max(maxL1, maxL2) + Math.min(minR1, minR2)) / 2;
} else if (maxL1 > minR2) hi = i - 1;
else lo = i + 1;
}
}
// Input: nums1=[1,3], nums2=[2] => Output: 2.0
// Input: nums1=[1,2], nums2=[3,4] => Output: 2.5
Time: O(log(min(m,n))) | Space: O(1)