Haiyang Yu's Blog
0%

Leetcode 69 Sqrtx

发表于 更新于 分类于 Valine：
本文字数： 708 阅读时长 ≈ 1 分钟

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

二分查找

将问题转化为, 从0到x中查找最后一个mid使得 mid * mid <= x的元素即可.

同时, 条件中要写mid <= x / mid 而不是mid * mid <= x, 否则mid*mid会溢出

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