69. Sqrt(x)

原题：69. Sqrt(x)

方法一

思路

二分法

要牢记二分法的模板：

let left = 0;
let right = arr.length-1;
while(left <= right) {
  let mid = (left + right) / 2;
  if(arr[mid] === target) {
    // find the target
    break or return result;
  }else if(arr[mid] < target) {
    left = mid + 1;
  }else {
    right = mid - 1;
  }
}

source code:

// Runtime: 88 ms, faster than 35.63% of JavaScript online submissions for Sqrt(x).
// Memory Usage: 36.1 MB, less than 11.11% of JavaScript online submissions for Sqrt(x).
var mySqrt = function (x) {
  let left = 0;
  let right = x;
  while (left <= right) {
    let mid = ~~((left + right) / 2);
    let tmp = mid * mid;
    if (tmp == x) {
      return mid;
    } else if (tmp < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return right;
};

拓展

求sqart(x)，要求精度为n

// init variable
while(Math.abs(right-left)< 1/Math.pow(10, n)) {// 退出条件为小于具体的精度
  let mid = (left + right) / 2;
  let tmp = mid * mid;
  if (tmp == x) {
    return mid;
  } else if (tmp < x) {
    left = mid;// 这里不能+1
  } else {
    right = mid;// 这里不能-1
  }
}

return left;

方法二

思路

牛顿迭代法：

这道题中，f(xn) = xn ^ 2 - y，f(xn)的导数 f'(xn) = 2 * xn。

最终可得：x(n+1) = (xn + y/xn)/2。

source code

// Runtime: 64 ms, faster than 95.63% of JavaScript online submissions for Sqrt(x).
// Memory Usage: 37.2 MB, less than 8.33% of JavaScript online submissions for Sqrt(x).
var mySqrt = function (x) {
  let r = x;
  while (r * r > x) {
    r = ~~((r + x / r) / 2);
  }

  return r;
};

test cases

test("test1", () => {
  expect(mySqrt(4)).toEqual(2);
});

test("test2", () => {
  expect(mySqrt(8)).toEqual(2);
});

test("test3", () => {
  expect(mySqrt(1)).toEqual(1);
});

test("test4", () => {
  expect(mySqrt(5)).toEqual(2);
});