Square root of a integer usining Binary Search

Problem Overview

Find the square root of positive integer x in O(log(N)) TC.

Note: Return the floor value of square root.

For exact problem visit Leetcode Link;

Sample Input Output

Input: x = 1
Output: 1

Input: x = 9
Output: 3

Input: x = 10
Output: 3

Javascript Solution

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 1
  let right = x
  let ans = 0

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

    const square = mid * mid

    if (square === x) {
      return mid
    } else if (square > x) {
      right = mid - 1
    } else {
      ans = mid
      left = mid + 1
    }
  }

  return ans
}

Problem Overview

Javascript Solution

Submission Result