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

Binary Search on Answer Technique

📖 Scenario: Imagine you have a list of wooden planks of different lengths. You want to cut these planks into smaller pieces of equal length so that you get at least a certain number of pieces. You want to find the longest possible length for these pieces.

🎯 Goal: Build a program that uses the binary search on answer technique to find the maximum length to cut the planks to get at least the required number of pieces.

📋 What You'll Learn

Create a slice called planks with the exact lengths: 4, 7, 9, 10, 15

Create an integer variable called requiredPieces and set it to 7

Write a binary search loop using low, high, and mid variables to find the maximum length

Print the final maximum length found

💡 Why This Matters

🌍 Real World

This technique helps in manufacturing and resource allocation where you want to optimize cutting or dividing materials.

💼 Career

Binary search on answer is a common pattern in coding interviews and software engineering tasks involving optimization.

1

Create the planks data

Create a slice called planks with the exact lengths: 4, 7, 9, 10, 15.

DSA Go

planks := []int{4, 7, 9, 10, 15} // Your code here

Hint

Use planks := []int{4, 7, 9, 10, 15} to create the slice.

2

Set the required number of pieces

Create an integer variable called requiredPieces and set it to 7.

DSA Go

package main

import "fmt"

func main() {
    planks := []int{4, 7, 9, 10, 15}
    requiredPieces := 7 // Your code here
}

Hint

Use requiredPieces := 7 to set the required number.

3

Implement binary search on answer

Write a binary search loop using variables low, high, and mid to find the maximum length to cut the planks so that the total pieces are at least requiredPieces. Use a for low <= high loop and calculate the total pieces by summing plank / mid for each plank.

DSA Go

package main

import "fmt"

func main() {
    planks := []int{4, 7, 9, 10, 15}
    requiredPieces := 7

    low := 1
    high := 15
    var result int

    // Your code here
}

Hint

Use a binary search loop with low, high, and mid. Calculate total pieces by summing plank / mid. Adjust low and high based on comparison with requiredPieces.

4

Print the maximum length

Print the variable result which holds the maximum length to cut the planks.

DSA Go

package main

import "fmt"

func main() {
    planks := []int{4, 7, 9, 10, 15}
    requiredPieces := 7

    low := 1
    high := 15
    var result int

    for low = requiredPieces {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    // Your code here
}

Hint

Use fmt.Println(result) to print the maximum length.