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

Question

我在java中写了一段代码来求m的n次方根，其中n和m都是整数。 1 <= n <= 30 , 1 <= 米 <= 10^9

如果根不是整数，那么我必须 return -1.

我的代码适用于较小的 m 和 n 值。但它失败了 n=6, m=4096 。我的代码 returns -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;

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

Finding Nth root of M using binary search in Java

java

integer-overflow

binary-search

nth-root