Binary Search Patterns

🔍 Binary Search Patterns: The Art of Finding Things Fast

The Story of the Smart Librarian

Imagine you’re in a huge library with 1,000 books arranged by number (1 to 1000). You need to find book #742.

The slow way: Check book 1, then 2, then 3… That could take 742 checks! 😓

The smart way: Go to the middle (book 500). Is 742 bigger or smaller? Bigger! So ignore all books 1-500. Now check the middle of what’s left (book 750). Is 742 bigger or smaller? Smaller! Keep going…

This is Binary Search - cutting your search in half each time! 🚀

🎯 Binary Search Fundamentals

The Core Idea

Binary search is like a guessing game. Someone thinks of a number between 1-100, and after each guess, they say “higher” or “lower.”

The magic rule: Always guess the middle! You’ll find ANY number in at most 7 guesses (for 1-100).

The Recipe

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

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;  // Found it!
    }
    if (arr[mid] < target) {
      left = mid + 1;  // Look right
    } else {
      right = mid - 1; // Look left
    }
  }
  return -1;  // Not found
}

Example: Finding 7

Array: [1, 3, 5, 7, 9, 11, 13]
        ↑           ↑
      left        right

Step 1: mid = 3 → arr[3] = 7 ✓ Found!

Key requirements:

• Array MUST be sorted
• Time: O(log n) - super fast!

🔄 Binary Search Variants

Sometimes you need more than “find this exact thing.” Here are the power moves:

Lower Bound (First occurrence)

Find the first position where target could be inserted.

function lowerBound(arr, target) {
  let left = 0, right = arr.length;

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

Upper Bound (After last occurrence)

Find the first position AFTER the target.

function upperBound(arr, target) {
  let left = 0, right = arr.length;

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

Example: Array with Duplicates

Array: [1, 2, 2, 2, 3, 4]
Target: 2

lowerBound(arr, 2) → 1 (first 2)
upperBound(arr, 2) → 4 (after last 2)
Count of 2s = 4 - 1 = 3 ✓

🌀 Search in Rotated Sorted Array

The Puzzle

Imagine a sorted array that got “rotated” - like spinning a wheel:

Original: [1, 2, 3, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 1, 2, 3]
                    ↑ rotation point

How do we search here? The trick: One half is ALWAYS sorted!

The Strategy

function searchRotated(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;

    // Check which half is sorted
    if (arr[left] <= arr[mid]) {
      // Left half is sorted
      if (target >= arr[left] && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > arr[mid] && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

Visual Example

[4, 5, 6, 7, 1, 2, 3]  Find: 2
 ↑        ↑        ↑
left     mid     right

arr[left]=4 <= arr[mid]=7 → Left is sorted
Is 2 in [4,7]? No! → Search right half

[1, 2, 3]
 ↑  ↑  ↑
 L  M  R → Found 2! ✓

📉 Find Minimum in Rotated Sorted Array

The Goal

Find the smallest element in a rotated array.

[4, 5, 6, 7, 1, 2, 3]
            ↑ This is what we want!

The Trick

The minimum is where the rotation “breaks” - where a bigger number is followed by a smaller one.

function findMin(arr) {
  let left = 0, right = arr.length - 1;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] > arr[right]) {
      // Min is in right half
      left = mid + 1;
    } else {
      // Min is in left half (including mid)
      right = mid;
    }
  }
  return arr[left];
}

Why This Works

[4, 5, 6, 7, 1, 2, 3]
        ↑           ↑
       mid        right

7 > 3 → The "break" must be on the right
        So minimum is in right half!

⛰️ Find Peak Element

What’s a Peak?

A peak is an element that’s bigger than its neighbors.

[1, 3, 5, 4, 2]
       ↑
     Peak! (5 > 3 and 5 > 4)

The Climbing Strategy

Think of climbing a hill. If you always walk toward the higher side, you’ll reach a peak!

function findPeak(arr) {
  let left = 0, right = arr.length - 1;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] < arr[mid + 1]) {
      // Slope going up → peak is on right
      left = mid + 1;
    } else {
      // Slope going down → peak is on left
      right = mid;
    }
  }
  return left;  // Index of peak
}

Visual Journey

[1, 2, 3, 4, 5, 3, 1]
          ↑
         mid

arr[4]=5 > arr[5]=3 → Going down!
Peak is to the left (including mid)
→ right = mid

🎯 Binary Search on Answer

The Big Idea

Sometimes you don’t search in an array - you search for the right answer in a range of possibilities!

Pattern:

1. Define min and max possible answers
2. Binary search for the smallest/largest answer that works
3. Check if an answer is valid with a helper function

Classic Example: Square Root

Find √x without using Math.sqrt:

function mySqrt(x) {
  if (x < 2) return x;

  let left = 1, right = Math.floor(x / 2);

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let square = mid * mid;

    if (square === x) return mid;
    if (square < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return right;  // Largest integer where square <= x
}

📦 Capacity To Ship Packages Pattern

The Problem

You have packages with weights. You need to ship them in order within D days. What’s the minimum ship capacity needed?

Packages: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Days: 5
Answer: 15 (can ship in 5 days with capacity 15)

The Strategy

1. Min capacity: largest single package (you must fit each one)
2. Max capacity: sum of all packages (ship in 1 day)
3. Binary search for the minimum capacity that works!

function shipWithinDays(weights, days) {
  let left = Math.max(...weights);
  let right = weights.reduce((a, b) => a + b);

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (canShip(weights, days, mid)) {
      right = mid;  // Try smaller capacity
    } else {
      left = mid + 1;  // Need bigger capacity
    }
  }
  return left;
}

function canShip(weights, days, capacity) {
  let daysNeeded = 1, currentLoad = 0;

  for (let w of weights) {
    if (currentLoad + w > capacity) {
      daysNeeded++;
      currentLoad = 0;
    }
    currentLoad += w;
  }
  return daysNeeded <= days;
}

How It Works

Capacity = 15, can we ship in 5 days?

Day 1: [1,2,3,4,5] = 15 ✓
Day 2: [6,7] = 13 ✓
Day 3: [8] = 8 ✓
Day 4: [9] = 9 ✓
Day 5: [10] = 10 ✓

Yes! 5 days work → try smaller capacity

✂️ Split Array Largest Sum

The Problem

Split an array into m parts to minimize the largest sum among them.

Array: [7, 2, 5, 10, 8]
Split into: 2 parts

Option 1: [7,2,5] and [10,8] → sums: 14, 18 → max = 18
Option 2: [7,2,5,10] and [8] → sums: 24, 8 → max = 24
Option 3: [7] and [2,5,10,8] → sums: 7, 25 → max = 25

Best: Option 1 with max = 18 ✓

Same Pattern, Different Question!

This is the same pattern as shipping packages!

function splitArray(nums, m) {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b);

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (canSplit(nums, m, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

function canSplit(nums, m, maxSum) {
  let parts = 1, currentSum = 0;

  for (let n of nums) {
    if (currentSum + n > maxSum) {
      parts++;
      currentSum = 0;
    }
    currentSum += n;
  }
  return parts <= m;
}

The Connection

Same code, different story! 🎉

🗺️ The Binary Search Pattern Map

graph LR
    A["Binary Search Patterns"] --> B["Exact Search"]
    A --> C["Boundary Search"]
    A --> D["Modified Arrays"]
    A --> E["Search on Answer"]

    B --> B1["Find target"]
    C --> C1["Lower Bound"]
    C --> C2["Upper Bound"]
    D --> D1["Rotated Search"]
    D --> D2["Find Min Rotated"]
    D --> D3["Find Peak"]
    E --> E1["Min Capacity"]
    E --> E2["Split Array"]

🎯 Quick Decision Guide

🚀 You’ve Got This!

Binary search isn’t just about finding things fast. It’s a thinking pattern:

1. ✅ Can I define a search space?
2. ✅ Can I eliminate half each step?
3. ✅ Can I check if an answer is valid?

If yes to these, binary search is your friend!

Remember: Every time you see “find minimum capacity” or “minimize maximum” - think binary search on answer! 💪