Square Root

1. Problem Description

Implement the function int sqrt(int x). Compute and return the square root of x, rounded down.

2. Approach

1. Approach 1
   • Traverse [1,x]
   • The current square is less than or equal to the target and the next square is greater than the target
2. Approach 2
   • Binary search

3. Implementation

3.1. Traversal

func mySqrt(x int) int {

	for i := 1; i <= x; i++ {
		now := i * i
		next := (i + 1) * (i + 1)

		if now <= x && next > x {
			return i
		}
	}

	return 0
}

3.2. Binary Search

func mySqrt(x int) int {
    left := 0
    right := x
    for left <= right {
        mid := left + (right-left)>>1
        current := mid * mid
        next := (mid+1) * (mid+1)
        if current <= x && next > x {
            return mid
        }else if current > x {
            right = mid - 1
        }else {
            left = mid + 1
        }
    }
    return 0
}

4. References

• Square Root - NowCoder
• Sqrt(x) - LeetCode