Sqrt(x)

음수가 아닌 정수 x가 주어지면 x의 제곱근을 계산하여 반환해야 합니다.
반환 유형이 정수이므로 소수 자릿수가 잘리고 결과 중 정수 부분만 반환됩니다.
참고: pow(x, 0.5) 또는 x ** 0.5와 같은 기본 제공 지수 함수 또는 연산자를 사용할 수 없습니다.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {

  if (x === 0) {
    return 0
  }
  let i = 1;

  while (i * i <= x) {
    i++
  }
  if (i > 1) {
    i--
  }

  return (i)
};

제곱근의 정수부분만 리턴하라는 조건으로 구간을 나눠 찾음

최다 추천 코드

  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;
};

이진탐색 이용