69. Sqrt(x)

# Easy

1. 暴力解法：从1到x循环

2. Binary search: 用loop写替代recursive

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        # edge case
        if x == 1:
            return 1
        
        #regular case
        start = 1
        end = x
        while start+1 < end:
            mid = start + (end-start)//2
            result = mid*mid
            if x == result:
                return mid
            if result < x:
                start = mid
            else:
                end = mid
                
        if start*start <= x:
            return start
        else:
            return end

Second Tab