Как избежать углового случая при решении идеального квадрата в O (lg N) времени?

Question

Следующий код находит, если данное число является идеальным квадратом в O (lg N). Как я могу избежать жесткого кодирования углового футляра if (num === 1) { return true; } в приведенном ниже решении? Есть идеи?

var isPerfectSquare = function(num) { 
    let floor = 0, ceiling = num, mid; 

    // Corner case 
    if (num === 1) { 
     return true; 
    } 

    while (floor != ceiling) { 
     mid = floor + (ceiling - floor)/2 | 0; 
     let mul = mid * mid; 

     if (mul === num) { 
      return true; 
     } 

     if (mul > num) { 
      ceiling = mid; 
     } 
     else if (mul < num) { 
      floor = mid+1; 
     } 
    } 
    return false; 
}; 

Answer 1

Сохраняя умный инвариант, мы можем изменить код, чтобы требовать проверок равенства только один раз, в конце концов. Должен работать для всех входных данных

var isPerfectSquare = function(num) { 
    let floor = 0, ceiling = num+1, mid; 
    // We will keep the invariants: floor*floor <= num, 
    // ceiling * ceiling > num 

    while (ceiling - floor > 1) { 
     mid = floor + (ceiling - floor)/2 | 0; 
     let mul = mid * mid; 

     // Move one of floor/ceiling to mid 
     // Retains the invariant! 
     if (mul > num) { 
      ceiling = mid; 
     } else { 
      floor = mid; 
     } 
    } 
    return floor * floor === num; 
}; 

Я, возможно, испортил синтаксис языка, но идея должна работать.

Answer 2

Вы можете избежать конкретной граничное случае для num==1, изменив условие в цикле в то время как для

while (floor < ceiling-1)

Этого будет достаточно, как если разница между floor & ceiling является 1, то вы будете запускается в бесконечный контур, так как floor + ceiling-floor/2 всегда будет равен floor при округлении

Я просто попытался с ниже реализаций Java и она выглядит хорошо

public static void isPerfectSquare(int num){ 
    int low = 0; 
    int high = num; 
    int mid; 
    while(low<high-1){ 
     mid = low + (high-low)/2; 
     System.out.println("high-- " + high + " low-- " + low + " mid---" + mid); 
     int square = mid*mid; 
     if(square==num){ 
      System.out.println("Found ->" + mid);   
      break; 
     } 
     else if(square<num){ 
      low = mid;   
     } 
     else if(square>num){ 
      high = mid;    
     }  
    } 
    }