Within the context of the interview question, the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. This is the error that my interviewer made. He was trained to deal with things within the context of situations closer to real life rather than the theoretical box he had established for the interviewing situation.
As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there.
My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.
As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there.
My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.