袋熊的树洞

日拱一卒，功不唐捐

0%

LeetCode 69 - Sqrt(x)

Posted on Edited on

问题描述

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.

Related Topics: Math, Binary Search

原问题: 69. Sqrt(x)

中文翻译版: 69. x 的平方根

解决方案

首先 $x$ 的平方根取值范围为 $[0, x]$，该区间中可能是 $x$ 的平方根的数要求满足其平方小于等于 $x$。题目中要求输出的是整数，此时问题变为在区间 $[0, x]$ 中寻找满足 $s^2 <= x$ 条件的最大的整数 $s$。

很自然地，我们可以从 $0$ 开始遍历，直到某个值的平方大于 $x$，此时前一个值就是所求的平方根，但是这种解法一般会超时。既然是在一个离散的区间内进行查找，并且区间的元素是有序的，此时我们可以用二分查找 (Binary Search) 快速找到我们想要的值。

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Use binary search to find the square root of x
 */

#include <iostream>
using namespace std;


class Solution {
public:
    int mySqrt(int x) {
        long long low, high, mid, square;

        // search in [low, high), so high = x + 1
        // use casting to avoid numerical overflow
        low = 0, high = (long long)x + 1;
        while (low < high) {
            mid = low + (high - low) / 2;
            square = mid * mid;
            if (square <= x)
                low = mid + 1;
            else
                high = mid;
        }
        return low - 1;
    }
};

int main()
{
    int x = 2147483647;
    Solution solu;

    cout << "Sqrt(" << x << ") = " << solu.mySqrt(x) << endl;
    return 0;
}

这里参考了知乎一个关于二分查找问题的回答 二分查找有几种写法？它们的区别是什么？，因为我们要找的是 $s^2 <= x$ (等价于 $s <= \sqrt{x}$) 的上界，所以参考了 upper_bound(value) - 1 的写法。