题目：

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example1：

Input:4
Output: 2

Example2：

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

---

思路：

此题采用二分法来做。首先求出中间元素值。然后用给定的值x分别除以中间值和中间值加一。得到的结果分别记为m1,m2。

• 如果m1等于中间值则返回m1。
• 如果m2等于中间值则返回中间值加一。
• 如果m1大于中间值并且m2小于中间值加一，则返回m1。

当m1<中间值，相当于中间值的平方大于给定值x。此时在左半区找。
当m1>中间值，相当于中间值的平方小于给定值x。此时在右半区找。

---

代码：

public int mySqrt(int x) {
        if(x <= 0)
            return 0;
        int start = 1;
        int end = x;
        while(start <= end){
            int mid = start + (end - start)/2;
            int m1 = x/mid;
            int m2 = x/(mid + 1);
            
            if(mid == m1)
                return m1;
            if(mid + 1 == m2)
                return mid + 1;
            if(m1 > mid && (mid + 1) > m2){
                return mid;
            }
            
            if(m1 < mid){
                end = mid;
            }else{
                start = mid + 1;
            }
        }
        return 1;
}