立方根

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/ada3edb4700143f4917d3e631ad2481a?tpId=196&tqId=40527&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        二分法寻找立方根
    复杂度：
        时间复杂度：O(logn)
        空间复杂度：O(1)
    """

    def cuberoot(self, n):
        # write code here
        left, right = 1, n

        while left < right:
            mid = left + (right - left) / 2
            if mid * mid * mid == n:
                return mid
            elif mid * mid * mid > n:
                right = mid - 1
            else:
                left = mid + 1

        return left if left * left * left <= n else left - 1


if __name__ == "__main__":
    sol = Solution()

    # n = 9

    # n = 8

    # n = 27

    n = 925414783

    res = sol.cuberoot(n)

    print res