This is the 20th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

Implement the int SQRT (int x) function.

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Example 1:

Input: 4 Output: 2Copy the code

Example 2:

Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

Solution: binary search

Their thinking

The square root of x is just finding the maximum value of KKK that is k2≤xk^2 ≤ xk2≤x.

Binary search for KKK, left set as 0, right set as X, mid take the average value of left + right, adjust left and right by comparison.

code

func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    l, r := 0, x
    res := - 1
    for l <= r {
        m := (l + r) / 2
        if m * m <= x {
            res = m
            l = m + 1
        } else {
            r = m - 1}}return res
}
Copy the code

The execution result

Execution time: 4 ms, beat 52.52% of users in all Go commits memory consumption: 2.2 MB, beat 61.82% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(logx)O(log x)O(logx), the number of binary search times.
  • Space complexity: O(1)O(1)O(1)

Topic link

69. Square root of x