/*
* @lc app=leetcode.cn id=69 lang=c
*
* [69] x 的平方根
*
* https://leetcode-cn.com/problems/sqrtx/description/
*
* algorithms
* Easy (34.81%)
* Total Accepted: 25.4K
* Total Submissions: 73.1K
* Testcase Example: '4'
*
* 实现 int sqrt(int x) 函数。
*
* 计算并返回 x 的平方根，其中 x 是非负整数。
*
* 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
*
* 示例 1:
*
* 输入: 4
* 输出: 2
*
*
* 示例 2:
*
* 输入: 8
* 输出: 2
* 说明: 8 的平方根是 2.82842...,
* 由于返回类型是整数，小数部分将被舍去。
*
*
*/
int mySqrt(int x) {
long i = ;
if(x==){
return ;
}
for(i=;i<=x/;i++){
if(i*i==x){
return i;
}
else if(i*i<x&&(i+)*(i+)>x){
return i;
}
}
return ;
}
这里要注意取值范围，用long比较合适。思路也挺简单的，循环到目标值的一半即可，然后两个判断，要么相等，要么当前值平方小于目标值，当前值加1的平方大于目标值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
python：
#
# @lc app=leetcode.cn id=69 lang=python3
#
# [69] x 的平方根
#
# https://leetcode-cn.com/problems/sqrtx/description/
#
# algorithms
# Easy (34.81%)
# Total Accepted: 25.4K
# Total Submissions: 73.1K
# Testcase Example: '4'
#
# 实现 int sqrt(int x) 函数。
#
# 计算并返回 x 的平方根，其中 x 是非负整数。
#
# 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
#
# 示例 1:
#
# 输入: 4
# 输出: 2
#
#
# 示例 2:
#
# 输入: 8
# 输出: 2
# 说明: 8 的平方根是 2.82842...,
# 由于返回类型是整数，小数部分将被舍去。
#
#
#
class Solution:
def mySqrt(self, x: int) -> int:
low = 0
mid = x // 2 # //代表整数除法
high = x
while low <= high: #注意判断条件
if mid * mid > x:
high = mid - 1
elif mid * mid < x:
low = mid + 1
else:
return mid
mid = (low + high) // 2
return mid #向下取整
python用的是二分法。