【LeetCode】69. Sqrt(x)

题目描述

Implement int sqrt(int x).

Compute and return the square root of x.

解题思路

二分。 每次找中间值，判断其平方与目标值的大小关系。

AC代码

class Solution { public: int mySqrt(int x) { int start = 0, end = x; while (start < end) { double mid = (start + end) / 2; if (mid * mid == x) return mid; else if (mid * mid < x) { if ((mid + 1) * (mid + 1) > x) return mid; else start = mid + 1; } else end = mid - 1; } return start; } };