题解 | 求平方根

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param x int整型
     * @return int整型
     */
    public int mysqrt (int x) {

        // 边界情况：x为0或1时，平方根就是自身
        if (x == 0 || x == 1) {
            return x;
        }

        // 二分查找的范围：left从0开始，right最大为x（实际√x一定≤x，缩小范围可设为x/2，但x=2时x/2=1更合理）
        int left = 0;
        int right = x;

        // 循环二分查找（左闭右闭区间 [left, right]）
        while (left <= right) {
            // 计算中间值（避免 left + right 溢出，用 left + (right - left)/2 等价于 (left + right)/2）
            int mid = left + (right - left) / 2;

            // 计算 mid²（用long存储，避免int溢出，例如x=2^30时，mid可能接近2^15，mid²约2^30，超过int范围）
            long square = (long) mid * mid;

            if (square == x) {
                // 找到精确平方根，直接返回
                return mid;
            } else if (square < x) {
                // mid² < x：说明可能存在更大的符合条件的数，搜索右半区间
                left = mid + 1;
            } else {
                // mid² > x：说明需要找更小的数，搜索左半区间
                right = mid - 1;
            }
        }

        // 循环结束时，left > right，此时right是最大的满足 right² ≤ x 的整数
        return right;
    }





}

思路：二分法 解决