Binary Search on Answer Technique in DSA C++ - Build from Scratch

Binary Search on Answer Technique

📖 Scenario: You are organizing a workshop and need to divide n identical items into k boxes. Each box must have the same number of items. You want to find the maximum number of items that can be placed in each box without leaving any box empty.

🎯 Goal: Build a program that uses the binary search on answer technique to find the maximum number of items per box that can be evenly distributed into k boxes.

📋 What You'll Learn

Create an integer variable n with value 100

Create an integer variable k with value 7

Create integer variables low and high for binary search range

Implement a binary search loop using low, high, and mid

Calculate how many boxes can be filled with mid items each

Adjust low and high based on the number of boxes filled

Print the maximum number of items per box found

💡 Why This Matters

🌍 Real World

This technique helps solve problems where you need to find the best possible value under constraints, like packing, scheduling, or resource allocation.

💼 Career

Binary search on answer is a common pattern in coding interviews and competitive programming, useful for optimizing solutions efficiently.

1

Setup the initial variables

Create two integer variables called n and k with values 100 and 7 respectively.

DSA C++

// Your code here

Hint

Use int n = 100; and int k = 7; to create the variables.

2

Initialize binary search range variables

Create two integer variables called low and high. Set low to 1 and high to n.

DSA C++

int n = 100;
int k = 7;
// Your code here

Hint

Set low to 1 because minimum items per box is 1, and high to n because maximum items per box cannot exceed total items.

3

Implement the binary search loop

Write a while loop that runs while low is less than or equal to high. Inside the loop, calculate mid as the average of low and high. Then calculate how many boxes can be filled with mid items each by dividing n by mid. If the number of boxes filled is at least k, set low to mid + 1. Otherwise, set high to mid - 1. Use integer division for calculations.

DSA C++

int n = 100;
int k = 7;
int low = 1;
int high = n;
// Your code here

Hint

Use a binary search loop to narrow down the maximum items per box.

4

Print the maximum items per box

Print the value of high using std::cout to display the maximum number of items per box.

DSA C++

int n = 100;
int k = 7;
int low = 1;
int high = n;

while (low = k) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
// Your code here

Hint

The final answer is stored in high after the loop ends.