本文共 1101 字，大约阅读时间需要 3 分钟。

题目描述

本题要求实现一个函数 int sqrt(int x)，用于计算给定整数 x 的整数平方根。该函数需要返回不大于 √x 的最大整数。

解法分析

为了高效地解决这一问题，可以采用二分搜索算法。这种方法的核心思想是通过不断缩小搜索范围来快速找到目标值。以下是详细的实现步骤：

代码实现

int sqrt(int x) {
    if (x < 0) return -1;
    if (x < 4) return x > 0 ? 1 : 0;
    
    long long rmin = 0;
    long long rmax = x / 2;
    
    while (rmin <= rmax) {
        long long rmid = (rmin + rmax) / 2;
        if (rmid * rmid == x) return rmid;
        if (rmid * rmid < x) rmax = rmid + 1;
        else rmin = rmid + 1;
    }
    
    return (int)rmin;
}

代码解释

• 边界条件处理：首先检查 x 的值。如果 x 为负数，直接返回 -1。对于小于 4 的正数，直接返回其平方根。
• 二分搜索：通过初始化 rmin 和 rmax，然后在 while 循环中不断调整搜索范围，计算中间值 rmid。
• 平方检查：根据 rmid 的平方与 x 的关系，调整搜索范围，最终找到最大的整数平方根。
• 返回结果：循环结束后，返回 rmin 作为整数平方根。

这种方法的时间复杂度为 O(log x)，在保证正确性的同时，能够高效地完成平方根计算。

转载地址：http://fqgyk.baihongyu.com/