[Leetcode] Sqrt(x)

Posted on by

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/

Leave a Reply