[LeetCode] 69. Sqrt(x)

https://leetcode.com/

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

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

 

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

• 0 <= x <= 2^31 - 1

Code:

var mySqrt = function(x) {
    if (x === 0 || x === 1) return x; // x가 0 또는 1인 경우에는 x를 반환
    let left = 1; // left 포인터를 1로 설정
    let right = Math.floor(x / 2); // right 포인터를 x의 절반으로 설정

    while (left <= right) { // 이진 탐색
        let mid = Math.floor((left + right) / 2); // 중간값 설정
        if (mid * mid === x) return mid; // mid의 제곱이 x와 같으면 mid 반환
        else if (mid * mid < x) left = mid + 1; // mid의 제곱이 x보다 작으면 left 업데이트
        else right = mid - 1; // mid의 제곱이 x보다 크면 right 업데이트
    }
    return right; // 최종적으로 right 반환
};

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode