More precisely, binary search (with a correct termination condition) takes "is there a circuit with cost less than X?" and answers "what is the minimum circuit cost?".

Going from there to "what is a minimum-cost circuit?" is a bit more work, but still polynomial:

  G' = G
  X = TSP-minimum-circuit-cost(G)
  for E in edges(G):
    if (exists-circuit-with-cost(G' minus E, X))
      G' = G' minus E
  return (G')