# 69-Sqrt(x)
###### tags: `Easy`
## Question
https://leetcode.com/problems/sqrtx/
## Key
* 因為平方根不可能超越數字本身，所以以0到數字本身(其實到x/2就可以了)為範圍，用二元搜尋來嘗試找並比較是否為平方根
* 要注意的是剛好不為平方跟的時候，二元搜尋找完不會是正確答案，所以答案不是mid，而是一個平方比x小的數，所以要取floor，是left-1
## Reference
## Solution

class Solution {
public:
    int mySqrt(int x) {
        if(x==1)
        {
            return 1;
        }
        long mid = 0;
        int left = 0;
        int right = x/2;
        while(left <= right)
        {
            mid = (left+right)/2;
            if(mid*mid == x)
            {
                return mid;
            }
            else if(mid*mid > x)
            {
                right = mid-1;
            }
            else
            {
                left = mid+1;
            }
        }
        return left-1;
    }
};