## Sunday, January 6, 2013

### [LeetCode] Sqrt(x) 解题报告

Implement `int sqrt(int x)`.
Compute and return the square root of x.
» Solve this problem

[解题思路]

2147395599

``````1:    int sqrt(int x) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int start =0, end;
5:      end= x/2<std::sqrt(INT_MAX)? x/2+1:std::sqrt(INT_MAX);
6:      while(start<= end)
7:      {
8:        int mid = (start+end)/2;
9:        int sqr = mid*mid;
10:        if(sqr ==x)
11:        {
12:          return mid;
13:        }
14:        if(sqr<x)
15:        {
16:          start = mid+1;
17:        }
18:        else
19:        {
20:          end = mid-1;
21:        }
22:      }
23:      return (start+end)/2;
24:    }
``````

``````1:       const float EPS = 0.000000001;
2:       int sqrt(int x) {
3:            // Start typing your C/C++ solution below
4:            // DO NOT write int main() function
5:            if(x==0) return x;
6:            float dividend = x;
7:            float val = x;//最终
8:            float last;//保存上一个计算的值
9:            do
10:            {
11:                 last = val;
12:                 val =(val + dividend/val) / 2;
13:            }while(abs(val-last) > EPS);
14:            int result = val;
15:            if(result * result > x)
16:                 result--;
17:            return result;
18:       }
``````

[Note]
1. Line 15 & 16