每天一道leetcode(Day 63)

69. x 的平方根

题目描述

实现  int sqrt(int x)  函数。

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

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

示例

• 示例 1:

输入: 4
输出: 2

• 示例 2:

输入: 8
输出: 2

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

解题思路

解题思路：二分法

代码模板：

left, right = 0, len(array) - 1
while left <= right:
    mid = (left + right) / 2
    if array[mid] == target:
        # find the target!!
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

代码

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

参考

69. x 的平方根