java - 在 Java 中使用二进制搜索查找 M 的第 N 个根

Question

我在 java 中编写了一个代码来查找 m 的第 n 个根，其中 n 和 m 都是整数。1 <= n <= 30 , 1 <= m <= 10^9

如果根不是整数，那么我必须返回 -1。

我的代码适用于 m 和 n 的较小值。但是对于 n=6, m=4096 它失败了。我的代码返回 -1，而正确答案是 4。我认为这是因为isProdGreater()方法中的溢出。我怎样才能防止这种溢出？

  public int NthRoot(int n, int m)
    {
        // code here
        int l = 1, h = m;
        
        int mid;
        while(l<h){
            mid = l + (h-l)/2;
            //long prod = pow(mid,n);
            if(isProdGreater(mid, n, m)){
                h = mid;
            }else{
                l = mid+1;
            }
        }
        
        if(l*l == m) return l;
        return -1;
    }
    
    boolean isProdGreater(int x, int n, int target){
        long a = 1;
        for(int i=0; i<n; i++){
            
            if(a*x >= target) return true;
            a = a*x;
        }
        return false;
    }

Answer 1

问题是你最后一次检查

if(l*l == m) return l;

这是检查平方，而不是 n 次方。你可能想要

if(Math.pow(l,n) == m) return l;