leetcode 69. x 的平方根

leetcode

二分查找：
C++：

class Solution {
public:
    int mySqrt(int x) {

        if ( x == 1 ) {

            return x;
        }
        
        int left = 0;
        int right = x;
        int middle = left + (right - left) / 2;
        while ( left < right ) {

            middle = left + (right - left) / 2;
            long long multiply = (long long)middle * middle;
            if ( middle == left || multiply == x ) {
                
                break;
            }
            
            if ( multiply < x ) {

                left = middle;

            } else {

                // multiply > x
                right = middle;
            }
        }

        return middle;
    }
};