Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

Given a non-negative integer, compute and return the square root of the number

Input: x = 4 Output: 2Copy the code

Ii. Analysis of Ideas:

Take half of the number each time and compare it with the current value. If the value is larger than the current value, the start value of the next time remains the same, and the end value decreases by 1. If less than the current value: the next starting value is increased by 1, and the end value remains the same.

function mySqrt(num) {
  let left = 0
  let right = num
  while (left <= right) {
    const mid = Math.floor((right - left) / 2) + left
    console.log(mid)
    const square = mid * mid
    if (square < num) {
      left = mid + 1
    } else if (square > num) {
      right = mid - 1
    } else {
      return mid
    }
  }
  return -1
}
Copy the code

When the code is finished, verify the code, input 4 and 9 will normally get results 2 and 3, as long as they are the full square root, but input 3 will have a problem, because the code uses math.floor and does not deal with accuracy issues, so 3 cannot calculate the correct result.

So if we don’t get the right answer using binary search, we can do it another way, we can do it recursively.

Take the square root of 3. Finally, the square root of 3 is approximately 1.732 (three decimal places reserved)

function sqrt(num) {
  function sqrtWrapper(min, max) {
    let current = (min + max) / 2;
    let nextMin = min, nextMax = max;
    if (current * current > num) {
      nextMax = current;
    } else {
      nextMin = current;
    }
    if (min === nextMin && max === nextMax) {
      return current
    }
    else if (nextMax - nextMin < Number.EPSILON) {
      return current;
    } else {
      returnsqrtWrapper(nextMin, nextMax); }}return sqrtWrapper(0, num);
}
Copy the code

Note the case where an infinite loop needs to be prevented due to floating-point calculation problems.

ES6 adds a tiny constant Number.EPSILON to the Number object. According to the specification, it represents the difference between 1 and the smallest floating point number greater than 1.

Iv. Summary:

Although binary lookup cannot correctly compute the square root of any number, only the complete square root can be processed, so we can use binary lookup to determine whether a number is the complete square root.

function isPerfectSquare(num) {
  let left = 0, right = num;
  while (left <= right) {
    const mid = Math.floor((right - left) / 2) + left;
    const square = mid * mid;
    if (square < num) {
      left = mid + 1;
    } else if (square > num) {
      right = mid - 1;
    } else {
      return true; }}return false;
};
Copy the code