Easy to understand JavaScript solution


  • 0
    H

    Just simple binary search.

    Remember that the square root of each X must happen within [1, x/2 + 1]

    So we can cut half at the first place.

      var mySqrt = function(x) {
      var left = 1;
      var right = Math.floor(x / 2) + 1;
      var mid;
    
      while (left <= right) {
        mid = Math.floor((left + right) / 2);
    
        if (mid * mid > x) {
          right = mid - 1;
        } else if (mid * mid < x) {
          left = mid + 1;
        } else {
          return mid;
        }
      }
    
      return right;
    };
    

    The tricky point is that we will return right if there is no square root found.

    The reason is the square root is between [n-1, n] and we can know that when while is broken right must be n-1


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.