🗓️ Day 15: Binary Search on Answers

🧠 Concept Deep Dive

What if we don't search in an array, but in a range of values to find the answer?

This is called Binary Search on the Answer — often used when:

• You need to minimize or maximize a condition
• You can check feasibility of a solution efficiently

It’s often combined with a helper function like canDo(mid).

🛠️ Pattern

1. Define the search space: low and high
2. While low < high, do:
   • Compute mid = Math.floor((low + high) / 2)
   • If condition is true at mid, update high = mid
   • Else, update low = mid + 1
3. Return low (or high, depending)

💡 Example Problem: Minimum Pages Allocation

🧩 Problem:

Given n books with pages[i] and m students, allocate books such that:

• Each student gets contiguous books
• Max pages assigned to a student is minimized

✨ Goal:

Minimize the maximum pages assigned to a student.

✅ Helper Function: isFeasible

function isFeasible(pages: number[], students: number, maxPages: number): boolean {
  let count = 1, total = 0;
  for (const page of pages) {
    if (page > maxPages) return false;
    if (total + page > maxPages) {
      count++;
      total = page;
    } else {
      total += page;
    }
  }
  return count <= students;
}

🔁 Binary Search on Answer

function findMinimumPages(pages: number[], students: number): number {
  let low = Math.max(...pages);
  let high = pages.reduce((a, b) => a + b);

  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (isFeasible(pages, students, mid)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return low;
}

🧪 Example

Input: pages = [10, 20, 30, 40], students = 2
Output: 60
Explanation: Allocate [10, 20, 30] and [40]

📊 Big O Complexity

Where n = number of books, sum = total pages

🧠 Real-world Analogy

Imagine you're assigning chapters to friends to summarize for a book club. You want to distribute the chapters so no one gets too much work. You try different maximum workloads (mid), and see if it's feasible to assign them within the given number of people.

🧪 LeetCode-style Homework

Problem: Capacity To Ship Packages Within D Days

function shipWithinDays(weights: number[], days: number): number {
  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b);

  const canShip = (capacity: number): boolean => {
    let day = 1, load = 0;
    for (const w of weights) {
      if (load + w > capacity) {
        day++;
        load = w;
      } else {
        load += w;
      }
    }
    return day <= days;
  };

  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (canShip(mid)) high = mid;
    else low = mid + 1;
  }

  return low;
}

📆 Summary

• Binary search isn’t just for arrays!
• Use it to find min/max feasible answers
• Needs a helper function to check feasibility

🔮 Up Next

▶️ Day 16: Two Pointers Technique