Searching & Graph Algorithms

Binary search, BFS, DFS, and dynamic programming — the core algorithms that appear in technical interviews and real-world systems.

Binary Search

// Binary Search — O(log n) time, O(1) space
// Requires sorted array. Halve the search space each iteration.
function binarySearch(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoids integer overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

// Find first occurrence (leftmost) of target
function binarySearchFirst(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) { result = mid; hi = mid - 1; } // keep searching left
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

// Search in rotated sorted array (e.g. [4,5,6,7,0,1,2])
function searchRotated(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    // left half is sorted
    if (arr[lo] <= arr[mid]) {
      if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else { // right half is sorted
      if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

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

BFS & DFS

type Graph = Record<string, string[]>;

const graph: Graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [], E: [], F: [],
};

// BFS — Breadth-First Search (level by level, uses queue)
// Use for: shortest path in unweighted graph, level-order traversal
function bfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>();
  const queue: string[] = [start];
  const order: string[] = [];
  visited.add(start);
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// DFS — Depth-First Search (go deep first, uses stack or recursion)
// Use for: cycle detection, topological sort, connected components
function dfs(graph: Graph, start: string, visited = new Set<string>()): string[] {
  visited.add(start);
  const order: string[] = [start];
  for (const neighbor of graph[start] ?? []) {
    if (!visited.has(neighbor)) {
      order.push(...dfs(graph, neighbor, visited));
    }
  }
  return order;
}

// Shortest path with BFS
function shortestPath(graph: Graph, start: string, end: string): string[] | null {
  const queue: string[][] = [[start]];
  const visited = new Set<string>([start]);
  while (queue.length > 0) {
    const path = queue.shift()!;
    const node = path[path.length - 1];
    if (node === end) return path;
    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([...path, neighbor]);
      }
    }
  }
  return null;
}

bfs(graph, 'A');  // ['A', 'B', 'C', 'D', 'E', 'F']
dfs(graph, 'A');  // ['A', 'B', 'D', 'E', 'C', 'F']

Dynamic Programming

// DP pattern: define state, recurrence, base case, fill order

// 1. Fibonacci (space-optimized)
function fib(n: number): number {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

// 2. Coin Change — minimum coins to reach amount — O(n * coins)
function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
coinChange([1, 5, 10, 25], 36); // 3 (25 + 10 + 1)

// 3. Longest Common Subsequence (2D DP) — O(m*n)
function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = s1[i - 1] === s2[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}
lcs('ABCBDAB', 'BDCAB'); // 4 (BCAB)

// 4. 0/1 Knapsack — O(n * capacity)
function knapsack(weights: number[], values: number[], capacity: number): number {
  const dp = Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = capacity; w >= weights[i]; w--) { // iterate backwards!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}
knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8); // 10