Binary Search on Answer Technique in DSA Javascript - Build from Scratch

Binary Search on Answer Technique

📖 Scenario: Imagine you are organizing a party and want to divide a list of guests into groups so that no group has more than a certain number of people. You want to find the smallest possible maximum group size that allows you to split all guests into a given number of groups.

🎯 Goal: Build a program that uses the Binary Search on Answer Technique to find the smallest maximum group size to split guests into a fixed number of groups.

📋 What You'll Learn

Create an array called guests with exact values: [10, 20, 30, 40, 50]

Create a variable called maxGroups and set it to 3

Write a function called canSplit that takes maxSize and returns true if guests can be split into at most maxGroups groups with each group sum ≤ maxSize, else false

Use binary search between low = max guest size and high = sum of all guests to find the smallest maxSize where canSplit(maxSize) is true

Print the final smallest maximum group size

💡 Why This Matters

🌍 Real World

This technique helps in tasks like dividing workloads, scheduling, or packing where you want to find an optimal limit by guessing and checking efficiently.

💼 Career

Binary Search on Answer is a common pattern in coding interviews and real-world optimization problems in software engineering and data analysis.

1

Create the guests array

Create an array called guests with these exact values: [10, 20, 30, 40, 50]

DSA Javascript

# Create the guests array with exact values
// Your code here

Hint

Use const guests = [10, 20, 30, 40, 50]; to create the array.

2

Set the maximum number of groups

Create a variable called maxGroups and set it to 3

DSA Javascript

const guests = [10, 20, 30, 40, 50];
// Create maxGroups variable and set it to 3
// Your code here

Hint

Use const maxGroups = 3; to set the number of groups.

3

Write the canSplit function

Write a function called canSplit that takes a parameter maxSize and returns true if the guests array can be split into at most maxGroups groups where the sum of each group is ≤ maxSize, otherwise returns false

DSA Javascript

const guests = [10, 20, 30, 40, 50];
const maxGroups = 3;
// Write the canSplit function below
// Your code here

Hint

Use a loop to add guests to current group sum. If sum exceeds maxSize, start a new group. Return false if groups exceed maxGroups.

4

Use binary search to find smallest max group size and print it

Use binary search with variables low set to the maximum value in guests and high set to the sum of all guests. Find the smallest maxSize where canSplit(maxSize) returns true. Print the final maxSize using console.log

DSA Javascript

const guests = [10, 20, 30, 40, 50];
const maxGroups = 3;

function canSplit(maxSize) {
    let groups = 1;
    let currentSum = 0;
    for (let i = 0; i  maxSize) {
            return false;
        }
        if (currentSum + guests[i]  maxGroups) {
                return false;
            }
        }
    }
    return true;
}

// Use binary search to find smallest maxSize and print it
// Your code here

Hint

Use binary search between max guest size and total sum. Update result when canSplit(mid) is true. Print result at the end.