69. Sqrt(x)

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.

Example 1:

Input: 4
Output: 2

Example 2:

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

 1 int mySqrt(int x) {
 2     int mid,low=1,high=x;
 3     if(x<2)
 4         return x;
 5     while(low<=high){
 6         //如果直接mid=(low+high)/2的话可能会溢出，数字够大的情况下 
 7         mid=low+(high-low)/2; 
 8         if(mid==x/mid)    break;
 9         else if(mid<x/mid)    low=mid+1;
10         else    high=mid-1;        
11     }
12     if(mid>x/mid)
13         return    mid-1;
14     else
15         return mid; 
16 }