#141 Sqrt(x)

题目描述：

Implement int sqrt(int x).

Compute and return the square root of x.

Have you met this question in a real interview?  Yes Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge 

O(log(x))

题目思路：

一道binary search题，boundary是1~x，然后不断缩小范围，就酱。

Mycode（AC = 11ms）：

class Solution { public: /** * @param x: An integer * @return: The sqrt of x */ int sqrt(int x) { // write your code here if (x == 0) return x; long long down = 1, upper = x; // 2, 2 while (down < upper) { long long mid = (down + upper) / 2; // 1 if (mid * mid <= x && (mid + 1) * (mid + 1) > x) { return mid; } else if (mid * mid < x) { down = mid + 1; } else { upper = mid - 1; } } return (int)down; } };