一起学算法-69. x 的平方根

一、题目

LeetCode-算法入门-69. x 的平方根
地址：https://leetcode-cn.com/problems/sqrtx/

难度：简单
实现 int sqrt(int x) 函数。

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

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

示例 1:
输入: 4
输出: 2

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

二、解题思路

由题意可知我们的解属于[0,x]区间的整数集合，因此可通过二分查找寻求答案。

三、实现过程

c++

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

PHP

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        $left = 0;
        $right = $x;
        $ans=0;
        while($left <= $right){
            $mid = (int)(($left + $right) / 2);
            if($mid*$mid <= $x){
                $left = $mid + 1;
                $ans = $mid;
            }else{
                $right = $mid - 1;
            }
        }
        return $ans;
    }
}

JavaScript

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
        var left = 0,right = x,ans=0;
        while(left <= right){
            var mid = Math.floor((left + right) / 2);
            if(mid*mid <= x){
                left = mid + 1;
                ans = mid;
            }else{
                right = mid - 1;
            }
        }
        return ans;
};

四、小结

本题涉及查找问题，采用二分查找的前提是有序序列。

分享不易，如果你觉得还有用就点个赞再走吧！