如何在 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

您可以通过将 while 循环中的条件更改为

来避免 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;             
         }       
     }
    }

Answer 2

通过保持智能不变量，我们可以将代码更改为最后只要求进行一次相等性检查。应该适用于所有输入

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

我可能搞砸了语言语法，但这个想法应该可行。

如何在 O(lg N) 时间内解决完美平方时避免极端情况？

How to avoid corner case while solving perfect square in O(lg N) time?

javascript

algorithm

big-o

binary-search