Implement
int sqrt(int x).
Compute and return the square root of x.
Easy question at the first glimpse, however, some corner cases can stop you for a long time. Apparently, should solve it using binary search. However, need to change a bit in a few places than normal binary search. For example, in following code, from line 4 -- line 9, we don't wait until l>=h to stop recursion, because, in that case, we may miss a few right solutions. Also, in line 17 and line 19, we don't increase low bound by one or decrease upper bound by one to ensure the middle position is still included in the next recursion.
Round 2 solution:
Using Newton's method, for details, refer to this post:
No comments:
Post a Comment