Why Binary Search as Divide and Conquer in DSA Typescript?

The Big Idea

What if you could find a needle in a haystack by looking at only a few spots?

The Scenario

Imagine you have a huge phone book and you want to find a friend's number. You start from the first page and check every name one by one until you find it.

The Problem

This manual way is very slow and tiring because you might have to look through thousands of pages. It wastes time and energy, especially if the book is very big.

The Solution

Binary Search splits the phone book in half each time you look. You check the middle page, decide which half your friend's name is in, and then only search that half. This way, you quickly zoom in on the right page without checking every single one.

Before vs After

✗ Before

function findNumber(names: string[], target: string): number {
  for (let i = 0; i < names.length; i++) {
    if (names[i] === target) return i;
  }
  return -1;
}

✓ After

function binarySearch(names: string[], target: string): number {
  let left = 0;
  let right = names.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (names[mid] === target) return mid;
    else if (names[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

What It Enables

It lets you find things super fast in big sorted lists by cutting the search space in half again and again.

Real Life Example

When you search for a word in a dictionary app, it uses binary search to jump quickly to the right page instead of flipping through every word.

Key Takeaways

Manual search checks every item one by one, which is slow.

Binary Search divides the list to find the target faster.

This method works only if the list is sorted.