Sqrt(x)

LeetCode #69

Description:

Implement int sqrt(int x).

Compute and return the square root of x.

Example:

Note

Idea:

就是sqrt的floor的integer。

二分法。但是其实写个对的code很tricky，看好code吧。

Code:

class Solution {
public:
    int mySqrt(int x) {
        if(x<2) return x;

        int left=1, right=x/2;
        int last_mid;

        while(left<=right){
            int mid = left+(right-left)/2;
            // 必须是这个顺序！
            if(mid<x/mid){
                left=mid+1;
                last_mid=mid;
            }
            else if(mid>x/mid){
                right=mid-1;
            }
            else{
                return mid;
            }
        }

        return last_mid;
    }
};