題目:

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x * * 0.5

給定一個數x,找出它的平方根,若是小數則無條件捨去

題目明文禁止built-in function
所以直接一行return int(sqrt(x))是不行的,雖然會過
既然sqrt不能用那就用二分搜在1~x的範圍中找出x的平方根

class Solution:
    def mySqrt(self, x: int) -> int:
        l=1
        r=x
        while l+1!=r:
            mid=(l+r)//2
            if mid*mid==x:
                return mid
            if mid*mid>x:
                r=mid
            if mid*mid<x:
                l=mid
        return l

一如往常,先設下限l=1跟上限r=x,mid定義為(1+r)//2
mid平方大於x,r降低到mid
mid平方小於x,l提高到mid
一旦mid平方等於x就回傳mid
若最後發現l+1=r(表示sqrt(x)是介於l和r之間的小數)
就取l(無條件捨去)
最後執行時間36ms(faster than 94.29%)

那我們下題見