Question

剑指 Offer II 072. 求平方根

题目描述

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

注意：本题与主站 69 题相同： https://leetcode.cn/problems/sqrtx/

解法

方法一

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

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

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

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

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

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