But how do you do your binary search on a set without enumerating/sorting it? For example, if at one step, you know that 28.3 is too small and 42 is too big, how do pick the number between them that will split your set in two?
A) Sort edges (descending).
B) Have a total order between N-sized subsets by treating each edge as a binary digit (1 if it is in, or 0 if it is not). I believe this guarantees that the total order between the binary numbers that correspond to edge selections is the same total order as the one between the sums of those selections.
C) Start with some first guess (e.g: 111...111000000...)
D) Binary search on the number, by adjusting each next guess to be the nearest number with N digits enabled.
I am not entirely sure, I just made this up, but I think it might work?