/*

 * @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 ;

}

#

# @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          #向下取整