LC69. x 的平方根

题目描述

题目描述：实现 int sqrt(int x) 函数，计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。示例：输入 8，输出 2（因为 8 的平方根是 2.828...，舍去小数得 2）。

思路解析

思路解析： 1. 核心思路：使用二分查找法在 [0, x] 区间内寻找平方最接近 x 的整数。因为平方根不会超过 x（x>=1 时），且单调递增，适合二分。 2. 关键点：注意整数溢出，mid*mid 可能超过 int 范围，使用 long 或 mid <= x/mid 避免乘法溢出。