1.题目

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

2.示例

示例 1：

输入：x=4

输出：2

 示例 2：

输入：x = 8

输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

---

 3.思路

二分法：

标准的面试题，考察的是二分法的使用，通过设置上界与下界不断寻找中值以寻找正确值。

4.代码

class Solution {public int mySqrt(int x) {int top = x;int bottom = 0;int ans=-1;while (bottom<=top){int mid = (top+bottom)/2;if ((long)mid*mid<=x){ans = mid;bottom = mid+1;}else{top = mid-1;}}return ans;}
}

---

会了？试试挑战下一题！♪（＾∀＾●）ﾉｼ （●´∀｀）♪

LeetCode150道面试经典题-- 二叉树的最大深度(简单)_Alphamilk的博客-CSDN博客