[LeetCode] 69. Sqrt(x)

Table of Contents

Description

Given a non-negative integer x, return the integer square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

Approach

Use binary search to locate the largest integer whose square does not exceed the input. Start with a lower(left) and upper bound(right) and repeatedly inspect the midpoint to decide which half contains the answer, narrow the range until the floor of the square root can be returned.

Solution

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  // The square root of x will be between 1 and x (inclusive).
  let left = 1,
    right = x;

  // If x is less than 2, its square root is x itself (for 0 and 1).
  if (x < 2) return x;

  // Perform binary search to find the integer square root.
  while (true) {
    const root = left + Math.floor((right - left) / 2);
    const square = root * root;

    // If the square is exactly x, we found the integer square root.
    if (square === x) return root;
    // If left and right are consecutive numbers, then 'left' is the integer square root.
    // This handles cases where x is not a perfect square, returning the floor of its square root.
    if (left + 1 === right) return left;

    // If the square is greater than x, the root is in the left half.
    if (square > x) right = root;
    // If the square is less than x, the root is in the right half.
    else left = root;
  }
};

Complexity Analysis

Time Complexity

The time complexity is O(log x) because with each iteration of the binary search, the search space is halved.

Space Complexity

The space complexity is O(1) since we are using a constant amount of extra space regardless of the input size.