Coding Challenge Practice - Question 111

The task is to implement Math.sqrt().

The boilerplate code

function mySqrt(x) {
  // your code here   
}

Convert whatever is input to a number

const num = Number(x)

If the input is negative or invalid, return NaN

if(isNaN(num)) {
 return NaN
}

if(num < 0) {
return NaN
}

If the input is 0 or 1, the square root is itself

if(num < 2) return num;

Binary search will be used to find the square root between 1 and the input

let left = 1;
let right = Math.floor((left + right) / 2);
let ans = 0

For any number greater than or equal to 2, the square root is less than or equal to half the number. That's why the upper boundary for the search is at half of the number; the square root can't be bigger than that.

To implement binary search, find the middle point of the search range

while(left <= right) {
const mid = Math.floor((left + right) / 2);
const square = mid * mid

If the square is equal to the original value, the middle point is the square root

if (square === num) {
 return mid;
}

If the square is less than the original value, search the right half. Otherwise, search the left half.

else if(square < num) {
    ans = mid;    
    left = mid + 1; 
  } else {
    right = mid - 1;
  }

The final code

function mySqrt(x) {
  // your code here  
  const num = Number(x);

  if(isNaN(num)) {
    return NaN;
  }

  if(num < 0) {
    return NaN;
  }

  if(num < 2) return x;

  let left = 1;
  let right = Math.floor(num / 2);
  let ans = 0;

  while(left <= right) {
    const mid = Math.floor((left + right) / 2);
    const square =  mid * mid;

    if(square === num) {
      return mid;
    } else if(square < num) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
    }
  return ans;
}

That's all folks!