The binary search is not a reduction, because you need to use TSP-decide a polynomial number of times (and for a reduction you reduce to one problem instance).

The binary search is not a reduction, because you need to use TSP-decide a polynomial number of times (and for a reduction you reduce to one problem instance). What you show is that your problem TSP-cost-optimize is in FP^NP (the class of function problems solvable in polynomial time with the help of an NP oracle).