leetcode--69. xの平方根

947 ワード

テーマ:69.xの平方根
リンク:https://leetcode-cn.com/problems/sqrtx/int sqrt(int x)関数を実装します.
xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.
例1:
  : 4
  : 2

例2:
  : 8
  : 2
  : 8       2.82842..., 
              ,        。

私の最初の反応は二分ですね.これでいいかどうか分かりません.二区分間【1,k】は、中点値の二乗がkより大きい場合は、半間区間を外し、そうでない場合は半間区間をとり、区間端点値が一差になるまで二分を継続する.
python:
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0 or x==1:
            return x
        low=1
        high=x
        while high-low>1:
            mid=(low+high)//2
            if mid*mid>x:
                high=mid
            else:
                low=mid
        return low