This is the 9th day of my participation in Gwen Challenge

The topic of dry

Implement the int SQRT (int x) function.

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Example 1:

Input: 4 Output: 2Copy the code

Example 2:

Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

Solution: binary search

When we take the square sum of a number, its square root must be in the range of this number, and our square root can only be rounded down, which requires us to judge middle, plus the result of the comparison with the next number of middle, if the number is greater than middle and less than middle+1, return middle.

Code implementation:

Execution time: 96 ms, beating 85.84% of users in all JavaScript commits

Memory consumption: 39.6 MB, beating 11.32% of all JavaScript commits

 var mySqrt = function (x) {
    let middle = 0;
    let high = x;
    let low = 1;
    if (x == 0) {
      return 0
    }
    while (low <= high) {
      middle = Math.floor((high + low) / 2);
      if (middle * middle == x || (x > middle * middle && x < (middle + 1) * (middle + 1))) {
        return middle
      } else if (middle * middle > x) {
        high = middle - 1
      } else {
        low = middle + 1}}};Copy the code