题目：
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;
}
