3 / 3 Binary Search On The Answer

The Gap At Two

Weights [1, 3, 3, 5]. possible(x) is true when some subset sums to exactly x:

x 0 1 2 3 4 5 6 7 8 9 10 11 12
possible yes yes no yes yes yes yes yes yes yes no yes yes

You want the smallest sum in [0,12][0, 12] that cannot be formed. Someone runs a standard first_true binary search over the predicate not possible(x) with lo = 0, hi = 12. It probes 6, then 10, then 8, then 9, and returns 10.

What went wrong?

A

The midpoint formula rounds the wrong way, so the search skipped past 2 on the very first probe.

B

possible is not monotone: it is false at 2, true again from 3 to 9, then false at 10. There is no threshold for a binary search to find, and the real answer is 2.

C

10 is correct. It is the smallest sum that would need a weight the multiset does not contain.

D

The bounds are wrong. Searching [0,13][0, 13] instead of [0,12][0, 12] finds 2.