leetcode with python:69. Sqrt(x)

题目:

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%)

那我们下题见