leetcode-69-Sqrt(x)

发表于   |  

描述

Implement int sqrt(int x).

Compute and return the square root of x.

分析

二分法，注意一下边界情况即可。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int mySqrt(int x) {
        int left = 1;
        int right = x / 2;
        if(x < 2) {
            return x;
        }
        while(left <= right) {
            int mid = left + (right-left)/2;
            if(x/mid > mid) {
                left = mid + 1;
            } else if(x/mid < mid) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return (left+right)/2;    
    }
};

解决方案2(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        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
            elif x/mid < mid:
                right = mid - 1
            else:
                return mid
        return (left+right)/2

相关问题

(M) Pow(x, n)

题目来源