Sqrt(x)

1，题目要求

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.

实现int sqrt（int x）。

计算并返回x的平方根，其中x保证为非负整数。

由于返回类型是整数，因此将截断十进制数字，并仅返回结果的整数部分。

2，题目思路

对于这道题，要求实现一个sqrt的函数模型。

在这个函数中，如果可以直接开方，就返回开方的值；如果不能直接开方，就返回取整后的结果。

如果我们直接使用暴力解法，即i*i的进行判断，自然是可以的，但是会造成大量不必要的时间消耗。

因此，一般来说，对于带有逐一便利和搜索的问题，我们一般可以使用二分搜索的思想，来解决这一问题。

需要注意的是，我们不是求正好的开方值，也即是不能以mid == x/mid为结束结果，而是找到小于准确开方值的最大整数。

3，代码实现

int x = []() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); class Solution { public: int mySqrt(int x) { if(x == 0 || x == 1) return x; int left = 0, right = x; int res = -1; while(left <= right){ int mid = left + (right - left)/2; if(mid > x/mid) right = mid-1; else{ left = mid+1; res = mid; } } return res; } };