Clojure - 161 chars
Solution using BigInteger arithmetic and successive squaring / square roots to home in on answer. I believe this usually results in less comparisons than binary search for large values of n - typically close to the number of bits in the binary representation of the answer, which is the theoretical optimum if you only have a binary comparison available.
(use'clojure.contrib.math)(defn find(loop[l 0 h nil](let[t(+(if h((exact-integer-sqrt(* l h))0)(* l l))1)](if(= l h)l(if(cmp t)(recur t h)(recur l(dec t)))))))
Expanded for readability:
(loop [l 0 h nil]
(let [t (+ (if h ((exact-integer-sqrt(* l h)) 0) (* l l)) 1)]
(if (= l h) l
(if (cmp t) (recur t h) (recur l (dec t)))))))
Note that the conciseness of the solution is considerably helped by the fact that Clojure automatically uses BigIntegers once values go outside the 64-bit long range.
; counter for compares
(def counter (atom 0))
; value to find
(def n 100000000000000000000000000000000000000000000000000000000)
; compare function
(defn cmp [x]
(swap! counter inc)
(<= x n)))
;let's find it!
; how many calls to cmp?
; how close to theoretical optimum?