题目描述(Easy)
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.
题目链接
https://leetcode.com/problems/sqrtx/description/
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的整数的开平方一定是大于1、小于x/2的，因此可以在[1,x/2]区间内使用二分查找来查找这个数。
提交代码：
class Solution { public: int mySqrt(int x) { int left = 1, right = x / 2; if (x < 2) return x; int mid, last_mid; while(left <= right) { mid = left + (right - left) / 2; if (mid > x / mid) right = mid - 1; else if (mid < x / mid) { last_mid = mid; left = mid + 1; } else return mid; } return last_mid; } };
