What you are describing isn't even a proper binary search, it just gives you a lower bound that is guaranteed to be no more than 50% smaller than the solution.
Let's assume doing an actual binary search. What you are getting, in every step of binary search using your oracle, is an upper bound U (D(TSP, U) ==1), for which we know that there is a solution smaller or equal that U, and a lower bound L (D(TSP, L) == 0) for which we know there isn't. This is where your confusion between finite and integer-valued comes into play: If the problem were integer valued, you would have the optimal solution S as soon as L_i=U_i (implying U_i is S), which would be guaranteed after a polynomial number of steps. With real valued weights, all you get is a sequence of intervals (L_1, U_1], (L_2, U_2], ... where the size of the intervals is halved in every step. What you actually want is the exact value of the solution. For that, you would need to show that there is no hamiltonian path between L_i and U_i, which isn't something your oracle can determine.
Note that this probably doesn't show that a polynomial oracle for the TSP decision problem will not yield a polynomial solution to the optimization problem in general, it just deals with your proposition.
Edit: Not -> Note
The set of all possible costs is the set of sums of all N-sized subsets of the edges.
You only need to binary search that set, not the real numbers' axis. The set's size is exponential to N, but binary searching is logarithmic, so it becomes polynomial in N.
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?
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?
Self balancing btrees will keep your set split roughly in half. So basically, you just insert elements and let the tree worry about remaining balanced.
This isn't a question of data structures: What bmichel is saying is that enumerating a nonpolynomial number of items isn't something you can do as a step in a polynomial reduction.
Let's assume doing an actual binary search. What you are getting, in every step of binary search using your oracle, is an upper bound U (D(TSP, U) ==1), for which we know that there is a solution smaller or equal that U, and a lower bound L (D(TSP, L) == 0) for which we know there isn't. This is where your confusion between finite and integer-valued comes into play: If the problem were integer valued, you would have the optimal solution S as soon as L_i=U_i (implying U_i is S), which would be guaranteed after a polynomial number of steps. With real valued weights, all you get is a sequence of intervals (L_1, U_1], (L_2, U_2], ... where the size of the intervals is halved in every step. What you actually want is the exact value of the solution. For that, you would need to show that there is no hamiltonian path between L_i and U_i, which isn't something your oracle can determine.
Note that this probably doesn't show that a polynomial oracle for the TSP decision problem will not yield a polynomial solution to the optimization problem in general, it just deals with your proposition. Edit: Not -> Note