[Leetcode] Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis

• 二分搜索 [0,x]
• 若 mid*mid 等于x，或者 (mid*mid<x && (mid+1)*(mid+1)>x), 则返回mid
• 否则若mid*mid < x，则搜索 [mid+1, right]
• 否则若mid*mid > x, 则搜索 [left, mid-1]
• 注意 mid*mid 可能会溢出，要用long类型
• Time: O(log n)
• Space: O(1)

Code

Reference
[1] https://leetcode.com/problems/sqrtx/