## 题目描述

• Implement int sqrt(int x).
• Compute and return the square root of x.

## 代码

`````` #include <iostream>
#include <cstdio>

using namespace std;

int sqrt(int x)
{
if(x < 1)
return 0;
if(x == 1)
return 1;
int start = 1;
int end = x;
int mid;
while(start <= end)
{
mid = (start + end) / 2;
if(x / mid == mid)
return mid;
if(mid < x / mid)
start = mid + 1;
else
end = mid – 1;
}
return (start + end) / 2;
}
int main()
{
int x;

#ifndef judge
freopen("in2.in","r",stdin);
freopen("std2.out","w",stdout);
#endif

while(cin>>x)
{
cout<<sqrt(x)<<endl;
}

#ifndef judge
fclose(stdin);
fclose(stdout);
#endif

return 0;
}
``````

## 代码二

`````` int sqrt(int x) {
long long i = 0;
long long j = x / 2 + 1;
while (i <= j)
{
long long mid = (i + j) / 2;
long long sq = mid * mid;
if (sq == x) return mid;
else if (sq < x) i = mid + 1;
else j = mid – 1;
}
return j;
}
``````

## 牛顿迭代法

``````int sqrt(int x) {
if (x == 0) return 0;
double last = 0;
double res = 1;
while (res != last)
{
last = res;
res = (res + x / res) / 2;
}
return int(res);
}
``````