Learning Divide & Conquer Algorithms

Introduction

Recently, I dove into divide-and-conquer algorithms, inspired by Grokking Algorithms. I wanted to understand not just how they work, but why they work and how to implement them efficiently.

Divide-and-conquer is all about breaking a problem into smaller subproblems, solving those recursively, and then combining the results. It’s elegant and incredibly powerful once you get the hang of it.

Tip: Visualize the array and indices on paper. It makes recursion and partitioning much easier to grasp.

Understanding Binary Search

Binary search was my first real “aha” moment. The idea is simple: split a sorted array in half, check the middle, and decide which half to search next. It felt like magic when I saw how quickly it narrowed down the search space.

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;

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

  return -1;
}

At first, I struggled with pointers — keeping track of left right mid Once I visualized it on paper, I realized the elegance: each comparison halves the search space. Super efficient!

Diving into Quicksort

Quicksort was more challenging but fun. The pivot, partitioning, and recursion made me think differently about arrays. Initially, I had to slow down and really feel the recursion.

function quicksort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left: number[] = [];
  const right: number[] = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  return [...quicksort(left), pivot, ...quicksort(right)];
}

Implementing it by hand helped me see each step unfold. Picking a pivot, partitioning the array, and combining results recursively felt like watching the algorithm in slow motion.

Pro tip: Understanding the indices and pointers i left right is key. Drawing them out really clarifies what’s happening.

My Takeaways

• Visualization helps: drawing the array and pivot movement clarified recursion.
• Divide and conquer isn’t scary: it’s just systematic problem breaking.
• Code first, then optimize: once I wrote a working solution, I could experiment with pivot strategies and in-place partitioning.

This experience made me more confident tackling not only sorting problems, but also any problem that can be broken into subproblems, which is a huge portion of algorithms in interviews and real-world coding.

I can now confidently approach problems like merge sort, quicksort, and binary search trees, and I understand the thought process behind why divide-and-conquer works so well.