[LeetCode] Sqrt 문제 - 자바스크립트 풀이

문제 링크

 

1. 접근방법

 

(1) mid를 제곱근으로 두고, low는 1, high는 x의 절반 값으로 둔다. 제곱근은 x의 절반보다 클 수 없다.

    let low = 1;
    let high = x / 2;
    let mid = 0;

 

(2) 기본 이진탐색을 진행한다. 단, low와 high를 옮기는 판단 기준은 mid * mid가 x보다 큰지 작은지로 설정한다.

    while (low <= high) {
        mid = Math.floor((high + low) / 2);
        if (mid * mid === x) return mid;
        if (mid * mid < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

 

(3) 만약 while문의 결과로 8의 제곱근 mid가 3으로 나오면 3의 제곱은 8보다 크므로 -1을 한 2를 리턴하도록 한다.

    if (mid * mid > x) return mid - 1;

 

(4) 1의 경우 제곱근을 1로 리턴하도록 예외처리를 추가한다.

    if (x <= 1) return x

 

2. 전체 풀이

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

이게 이진탐색 문제인 걸 파악하는데 이틀걸림 화남