Searching Algorithms

Searching algorithms locate a target value within a data structure. The right choice depends on whether the data is sorted, how large it is, and how often you search versus update.

Linear Search — O(n)

Linear search checks every element until it finds the target. It works on any array, sorted or not, and is the only option when the data has no defined order.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

linearSearch([4, 2, 7, 1, 9], 7); // 2

Binary Search — O(log n)

Binary search requires a sorted array. It repeatedly halves the search space by comparing the middle element to the target. Each comparison eliminates half of the remaining candidates, making it extremely efficient on large datasets.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = (left + right) >> 1;        // bit-shift avoids overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

binarySearch([1, 3, 5, 7, 9, 11], 7); // 3

Binary Search Variants

Many interview problems require finding the first or last occurrence, or the insertion point — not just a yes/no answer.

// Find the leftmost index where arr[i] >= target
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // insertion point
}

// Find the rightmost index where arr[i] === target
function findLast(arr, target) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) { result = mid; lo = mid + 1; }
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

Searching in 2D Sorted Arrays

A matrix where each row and column is sorted can be searched in O(m + n) by starting at the top-right corner.

function searchMatrix(matrix, target) {
  let row = 0, col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) return [row, col];
    if (matrix[row][col] > target) col--;
    else row++;
  }
  return null;
}

Hash-Based Search — O(1) average

For frequent lookups without range queries, a hash map gives O(1) average-case search. The trade-off is O(n) extra space and no ordering.

const index = new Map(items.map((item, i) => [item.id, i]));
// O(1) lookup instead of O(n) scan
const pos = index.get(targetId);

Choosing the Right Search

• Unsorted, small: linear search
• Sorted array: binary search O(log n)
• Frequent lookups, no order needed: hash map O(1)
• Prefix lookups on strings: Trie
• Nearest neighbour / range queries: BST or segment tree