一起刷leetcode(69):求根号Sqrt(x)


原题地址:https://oj.leetcode.com/problems/sqrtx/
原题编号:69
问题描述:
Implement int sqrt(int x) .
Compute and return the square root of x.

提示:二分查找
已邀请:

sumnous - 数据挖掘女博士

赞同来自: July beta LostOsiris leonguo debug123 wsk更多 »


思路:二分查找

Python代码(已AC):
class Solution:
    # @param x, an integer
    # @return an integer
    def sqrt(self, x):
        left = 1
        right = x / 2
        if x < 2: 
            return x
        while left <= right:
            mid = left + (right - left) / 2
            if (x / mid) > mid:
                left = mid + 1
                last_mid = mid
            elif (x / mid) < mid:
                right = mid - 1
            else:
                return mid
        return last_mid


坚持不懈刷Leetcode!Leetcode题目必答!

要回复问题请先登录注册