LeetCode #69 Sqrt(x)

問題概要

入力値：x(int)
出力値：int
問題のリンク

入力例

x: 4
answer: 2

解答例1

Binary search
計算量：O(logn)
Python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 0
        right = x
        while left <= right:
            mid = (left + right) // 2
            if mid * mid < x:
                left = mid + 1
            elif mid * mid > x:
                right = mid - 1
            else:
                return mid
        return right

Runtime: 9ms
Beats: 94.50%