【c++leetcode】69. Sqrt(x)

问题入口

二分搜索

最困难的是能否意识到用二分搜索法解题。

算术平方根的区间在[1, x] 。代码如下：

class Solution {
public:
    int mySqrt(int x) {
        if (x == 1 || x == 0)
        {
            return x;
        }
        
        int64_t start = 1;
        int64_t end = x;
        while (start <= x)
        {
            int64_t mid = start + (end - start) / 2;
            if (mid * mid  < x)
            {
                if ((mid + 1) * (mid + 1) > x)
                    return mid;
                
                start = mid + 1;
            }
            else if(mid * mid  > x)
            {
                if ((mid - 1) * (mid - 1) < x)
                    return mid - 1;
                end = mid - 1;
            }
            else
                return mid;
        }
        
        return 0;
    }
};

关于时间复杂度

以中间的元素为界，如果大于中间元素，范围限定在右半边，如果小于中间元素，范围限定在左半边。假设数组元素数为n，范围依次是 $n\rightarrow \frac{n}{2}\rightarrow \frac{n}{4}\rightarrow ...\rightarrow 1$ 。假设通过k次找到指定元素， $\frac{n}{2^{k}} = 1, k=log_{2}n$ 。时间复杂度为O(logn)

溢出

题目要求 $0<=x<=2^{31}-1=2147483647$

#include <cstdint>
#include <iostream>

int main() {
    int8_t a = INT8_MAX;
    int16_t b = INT16_MAX;
    int32_t c = INT32_MAX;
    int64_t d = INT64_MAX;

    std::cout << "Maximum value of int8_t: " << +a << std::endl;
    std::cout << "Maximum value of int16_t: " << b << std::endl;
    std::cout << "Maximum value of int32_t: " << c << std::endl;
    std::cout << "Maximum value of int64_t: " << d << std::endl;

    return 0;
}