69. x 的平方根

English Version

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解法

Python3

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        low, high = 1, x
        while low < high:
            mid = (low + high + 1) >> 1
            # mid * mid <= x
            if x // mid >= mid:
                low = mid
            else:
                high = mid - 1
        return low

Java

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int low = 1, high = x;
        while (low < high) {
            int mid = (low + high + 1) >>> 1;
            if (x / mid >= mid) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

JavaScript

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x == 0) {
        return 0;
    }
    let low = 1;
    let high = x;
    while (low < high) {
        const mid = low + ((high - low + 1) >> 1);
        if (x / mid >= mid) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return low;
};

Go

func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	low, high := 1, x
	for low < high {
		mid := low + (high-low+1)>>1
		if x/mid >= mid {
			low = mid
		} else {
			high = mid - 1
		}
	}
	return low
}

C#

public class Solution {
    public int MySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int low = 1, high = x;
        while (low < high)
        {
            int mid = low + ((high - low + 1) >> 1);
            if (x / mid >= mid)
            {
                low = mid;
            } 
            else 
            {
                high = mid - 1;
            }
        }
        return low;
    }
}

...