2 / 3 Binary Search On The Answer

Eighteen Across Two Pieces

Split [7, 2, 5, 10, 8] into 2 contiguous pieces so that the largest piece sum is as small as possible. Search over the answer: feasible(cap) walks left to right, starting a new piece whenever adding the next element would exceed cap, and reports whether the piece count is at most 2. Bounds start at lo = 10 (the largest element) and hi = 32 (the total).

step lo hi mid feasible(mid) action
1 10 32 21 yes, pieces [7,2,5] and [10,8] hi = 21
2 10 21 15 no, 3 pieces needed lo = 16
3 16 21 18 yes hi = 18

What is the final answer, and how many feasible calls does the search make in total?

A

21, after 3 calls

B

18, after 4 calls

C

18, after 3 calls

D

17, after 4 calls