69 Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Solution:

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, n;
        while ( true ) {
            n = (l+r)/2;
            if ( pow(n, 2) <= x and pow((n+1), 2) > x ) return n;
            if ( pow(n, 2) > x ) r = n;
            if ( pow((n+1), 2) <= x) l = n;
        }
        return n;
    }
};

Notes

• Binary search!
• 注意溢出的问题，
  • 用pow(n, 2)可以避免这个问题；
  • 否则应该采用长整型long.