Searching, Sorting, and Recursion

Introduction

This is lesson 3 of chapter 9 (domain interview). Lesson 2 gave you the containers; this lesson gives you the classic algorithms that operate on them: searching, sorting, and recursion, along with the techniques that make them efficient (binary search, divide and conquer, memoization). The official ninth course covers algorithms as one of its four topics (source: https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)). The explanations and problems here are original and are framed around interface work, so you can connect them to code you already write.

Learning objectives

By the end of this lesson you can:

1. Implement linear search and binary search and state when each applies.
2. Avoid the common off-by-one and overflow-style mistakes in binary search.
3. Explain bubble, insertion, merge, and quick sort and their complexities.
4. Use Array.prototype.sort correctly, including the comparator and its default string behavior.
5. Write recursive functions with a base case and a progress step.
6. Convert between recursion and iteration and explain stack depth.
7. Use memoization to remove repeated work in overlapping subproblems.
8. Solve problems with sliding window and sort-then-scan patterns.

1. Linear search and binary search

Linear search checks each item until it finds the target: O(n) time, O(1) space, works on any array.

Binary search works only on sorted data. It compares the target with the middle element and discards half of the remaining range each step: O(log n) time. For 1,000,000 items that is about 20 comparisons instead of up to 1,000,000.

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Trace with [3, 8, 15, 21, 34, 55, 89] and target 34:

low=0 high=6 mid=3 -> 21 < 34 -> low=4
low=4 high=6 mid=5 -> 55 > 34 -> high=4
low=4 high=4 mid=4 -> 34 found, return 4

Where binary search goes wrong

• Using low < high instead of low <= high skips the case where one element remains.
• Setting low = mid or high = mid instead of mid + 1 / mid - 1 can loop forever.
• Running it on unsorted data returns wrong answers without any error.
• Forgetting the empty array: high = -1, the loop never runs, and -1 is returned correctly.

Binary search for a boundary

Often you want the first position meeting a condition, such as the first session starting at or after 14:00 (840 minutes) in a sorted list.

function firstAtOrAfter(sortedTimes, minute) {
  let low = 0;
  let high = sortedTimes.length;       // note: length, not length - 1
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (sortedTimes[mid] < minute) low = mid + 1;
    else high = mid;
  }
  return low;                          // length means "none"
}

For [540, 660, 780, 900, 1020] and 840, the answer is index 3 (900). This variant keeps high as an exclusive bound, which is why the loop uses < and high = mid.

2. Sorting

Sorting puts items in order so that later steps (binary search, duplicates, merging) become cheap.

A sort is stable when equal items keep their original relative order. Stability matters for multi-key sorting, such as sorting workshops by level after sorting by title.

Insertion sort

function insertionSort(items) {
  const a = [...items];                       // do not mutate the input
  for (let i = 1; i < a.length; i++) {
    const value = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
  return a;
}

Good for tiny or nearly sorted lists; poor for large random data.

Merge sort

Divide and conquer: split the array in half, sort each half recursively, then merge two sorted halves.

function mergeSort(items) {
  if (items.length <= 1) return items;          // base case
  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid));
  const right = mergeSort(items.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);  // <= keeps it stable
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

The array is halved log₂ n times, and each level merges n items in total, so O(n log n). It needs O(n) extra space.

Quick sort in words

Choose a pivot, move smaller items to its left and larger to its right, then sort each side recursively. Average O(n log n); the worst case O(n²) happens with consistently bad pivots (for example, an already sorted array with the first element as pivot). In an interview, explain this idea and the worst case; implement it only if asked.

Array.prototype.sort in JavaScript

The built-in sort is stable in modern engines and runs in O(n log n) time. Two pitfalls matter:

[10, 9, 1, 100].sort();                 // [1, 10, 100, 9]  - converts to strings!
[10, 9, 1, 100].sort((a, b) => a - b);  // [1, 9, 10, 100]

Without a comparator, items are compared as strings. A comparator returns a negative number if a goes first, positive if b goes first, and zero if equal. Also, sort mutates the array. In React state, copy first or use toSorted where available:

const sorted = [...workshops].sort((a, b) => a.title.localeCompare(b.title));

localeCompare handles accented and case-different text more correctly than < on strings.

3. Recursion

A recursive function calls itself on a smaller version of the problem. Every correct recursion has:

1. A base case that returns directly.
2. A recursive case that moves toward the base case.

function sumTo(n) {
  if (n <= 0) return 0;        // base case
  return n + sumTo(n - 1);     // progress: n shrinks
}

Trace sumTo(3):

sumTo(3) = 3 + sumTo(2)
         = 3 + (2 + sumTo(1))
         = 3 + (2 + (1 + sumTo(0)))
         = 3 + (2 + (1 + 0)) = 6

Each call waits on the call stack. Depth n means O(n) stack space, and a very large n (tens of thousands) throws a RangeError: Maximum call stack size exceeded. An iterative loop uses O(1) space for the same job.

Recursion on nested data

Recursion shines where the data is nested, such as comment threads or a file tree.

function countComments(comment) {
  let total = 1;
  for (const reply of comment.replies) total += countComments(reply);
  return total;
}

countComments({
  text: 'Great class',
  replies: [{ text: 'Agree', replies: [] }, { text: 'Which room?', replies: [{ text: 'B2', replies: [] }] }],
}); // 4

Flatten a nested array

function flatten(value) {
  const out = [];
  for (const item of value) {
    if (Array.isArray(item)) out.push(...flatten(item));
    else out.push(item);
  }
  return out;
}
flatten([1, [2, [3, 4]], 5]); // [1, 2, 3, 4, 5]

(array.flat(Infinity) does the same; the point is being able to explain it.)

4. Worked example: Fibonacci and memoization

Problem. Return the nth Fibonacci number, where fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2).

Naive recursion.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Analysis. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again. The same subproblems are recomputed many times, so the number of calls grows exponentially, roughly O(2ⁿ). fib(45) already needs over a billion calls.

Fix 1: memoization. Cache results by input.

function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n);
  const value = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, value);
  return value;
}

Each n is computed once: O(n) time, O(n) space for the cache plus recursion depth.

Fix 2: iteration.

function fibIter(n) {
  let previous = 0;
  let current = 1;
  for (let i = 0; i < n; i++) {
    [previous, current] = [current, previous + current];
  }
  return previous;
}

O(n) time, O(1) space. Trace fibIter(4): (0,1) → (1,1) → (1,2) → (2,3) → (3,5), returns 3.

Why the alternatives are weaker. Naive recursion is correct but unusable beyond small inputs. Memoization is excellent when subproblems overlap and the recursion is natural. Iteration is best when only the final value is needed and memory matters. Your interview answer should name all three and recommend one for the stated constraints.

Front-end connection. useMemo and React.memo apply the same idea: reuse a previous result when the inputs did not change. Memoization is only worth it when the computation is expensive or the reference stability prevents re-renders; adding it everywhere costs memory and complexity.

5. Sliding window and sort-then-scan

Sliding window

A sliding window keeps a contiguous range and moves it one step at a time, updating a running value instead of recomputing it.

Problem. Given daily visitor counts, find the highest total over any k consecutive days.

function bestWindow(counts, k) {
  if (k > counts.length) return null;
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += counts[i];
  let best = windowSum;
  for (let i = k; i < counts.length; i++) {
    windowSum += counts[i] - counts[i - k];   // add new day, drop oldest
    best = Math.max(best, windowSum);
  }
  return best;
}
bestWindow([4, 9, 2, 7, 5, 1], 3); // 14 (9 + 2 + 7)

O(n) time and O(1) space, compared with O(n·k) when each window is summed from scratch.

Sort, then scan

Sorting turns many "compare everything" problems into a single pass.

Problem. Merge overlapping booking intervals: [[9,12],[11,14],[16,18]] becomes [[9,14],[16,18]].

function mergeIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else merged.push([start, end]);
  }
  return merged;
}

Sorting costs O(n log n); the scan is O(n); total O(n log n). Without sorting, comparing every pair would be O(n²). Note the Math.max: [1,10] followed by [2,3] must stay [1,10].

6. Choosing between iteration and recursion

JavaScript engines do not reliably optimize tail calls, so do not rely on "tail recursion" to avoid stack growth.

7. Common pitfalls and exam tips

Exam tip: for binary search, say the precondition ("sorted") and the invariant ("if the target exists, it is within low..high") aloud.

Exam tip: for recursion, state the base case first, then show that each call gets closer to it.

Pitfalls:

• Calling sort() on numbers without a comparator.
• Mutating state with sort or reverse in React.
• Infinite recursion from a missing or unreachable base case.
• Binary search on unsorted data, or an off-by-one in the bounds.
• Using recursion for a very deep structure without considering stack limits.
• Memoizing with a cache that never gets cleared in a long-running app (memory growth).
• Assuming quick sort is always O(n log n).
• Forgetting that slice in a recursive function copies and adds cost.

8. Mini case study: the sorted, searchable price list

Situation. Harbor Workshops shows up to 50,000 sessions sorted by start time. Requirements: (1) jump to the first session at or after a chosen time; (2) show a list sorted by price, ties broken by title; (3) a developer proposes computing a nested menu depth with recursion on user-uploaded data.

Solution, commented.

1. Jump to a time. The data is already sorted, so binary search for the boundary (firstAtOrAfter, section 1). Cost O(log n) ≈ 16 comparisons instead of scanning up to 50,000 items on every click.
2. Sort by price, then title. Use one comparator that handles both keys, which is stable and clearer than two passes:

const byPriceThenTitle = (a, b) =>
  a.price - b.price || a.title.localeCompare(b.title);
const view = [...sessions].sort(byPriceThenTitle);

Cost O(n log n). Copy the array so React state is not mutated. Cache the sorted view with useMemo keyed on sessions so it is recomputed only when the data changes, not at every keystroke.

3. Recursion on uploaded data. The depth is user-controlled, so a malicious or buggy input could be 100,000 levels deep and crash the page with a stack overflow. Use an iterative traversal with an explicit stack, or reject input deeper than a safe limit (for example 100) with a clear message.

function maxDepth(root) {
  let best = 0;
  const stack = [[root, 1]];
  while (stack.length > 0) {
    const [node, depth] = stack.pop();
    best = Math.max(best, depth);
    for (const child of node.children) stack.push([child, depth + 1]);
  }
  return best;
}

4. Verification. Test empty lists, a single session, times before the first and after the last session (expect index 0 and length), equal prices with different titles, and a deliberately deep tree.

Key terms

• Binary search: halving a sorted range to find a value in O(log n).
• Stable sort: equal items keep their original order.
• Comparator: a function that defines ordering for sort.
• Divide and conquer: split a problem, solve parts, combine.
• Base case: the input at which recursion stops.
• Call stack: memory that tracks active function calls.
• Memoization: caching function results by input.
• Sliding window: a moving range updated incrementally.

Summary checklist

• I can write binary search without off-by-one errors and state its precondition.
• I can compare bubble, insertion, merge, and quick sort.
• I always pass a comparator to sort for numbers and copy before sorting state.
• I write recursion with a clear base case and progress step.
• I recognize overlapping subproblems and apply memoization.
• I can use sliding window and sort-then-scan to avoid O(n²).
• I can explain when to prefer iteration to avoid stack overflow.

Sources

• Coding Interview Preparation (official course): https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)
• MDN Array.prototype.sort: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort (opens in a new tab)
• MDN Recursion: https://developer.mozilla.org/en-US/docs/Glossary/Recursion (opens in a new tab)