给定一个数 N 和一个排序数组 A，检查 A 中是否有两个数的乘积为 N

Question

给定一个数字N和一个排序数组A，设计一个算法-使用分而治之方法-检查是否存在索引i 和索引 j 使得 A[i]*A[j] == N （return 如果存在则为 1，如果不存在则为 0）。

我很难按照要求的（递归）方式进行。我想我只找到了一个可能解决方案的一部分，但即使在那里我也不能 100% 确定它是否正确：我认为如果第一个元素和数组的中心元素之间的乘积大于 N，那么我正在寻找的数字（如果存在）肯定在数组的前半部分，所以我可以递归地调用该部分的函数，就像这样（我正在使用 C）：

int productN(int A[], int i, int j, int N){

    // missing base case

    int m = (i+j)/2;
    
    if(A[i]*A[m] > N){
        return productN(A, i, m, N);
    } else{
        // do something else
    }
}

int main(){

    int A[]={1, 2, 3, 4, 5};
    printf("%d\n", productN(A, 0, 4, 15));  // initial value for i and j are the first and last index of the array

    return 0;

}

除此之外，我被困住了，我什至想不出一个基本案例，所以非常感谢任何帮助，谢谢。

编辑：根据您非常有帮助的回答，使用二进制搜索，我想我明白了：

int productN(int A[], int i, int j, int N){
    
    int m = (i+j)/2;    // central element of the current array
    
    int x;
    for(x=i; x<=m; x++){
        if(N%A[x]==0 && binarySearch(A, m, j, N/A[x]))
            return 1;
    }
        
    if(i!=j){
        if(productN(A, i, m, N) || productN(A, m+1, j, N))
            return 1;
    }
    
    return 0;

}

好看吗？还能更好吗？

编辑：我问这个问题已经有一段时间了，但我写了另一个解决方案，阅读起来更简单。我会把它留在这里，以防有人感兴趣。

int productN(int A[], int i, int j, int N, int size){
    
    if(i==j){        // base case
        if(N%A[i]==0)
            return binarySearch(A, 0, size-1, N/A[i]);
        else
            return 0;
    }
        
    int m = (i+j)/2; 
    
    if((N%A[m])==0){
        if(binarySearch(A, 0, size-1, N/A[i]))
            return 1;
    }
    
    return productN(A, i, m, N, size) || productN(A, m+1, j, N, size);

}

Answer 1

使用分而治之，您可以使用类似于归并排序算法的方法。正如评论所暗示的那样，有更简单的方法。但如果分而治之是必须的，这就足够了。
（本人C不精通，直接写算法）

def productN(arr):
    x = len(arr)
    left_half = arr[0:x/2]
    right_half = arr[x/2:]
    if productN(left_half) or productN(right_half):
        return True
    for i in left_half:
        if N%i==0 and binary_search(right_half, N/i):
            return True
    return False

给定一个数 N 和一个排序数组 A，检查 A 中是否有两个数的乘积为 N

Given a number N and a sorted array A, check if there are two numbers in A whose product is N

c

arrays

algorithm

recursion

divide-and-conquer