分而治之——返回一个数组

Question

我最近正在研究分而治之算法。

如果 return 值应该是某个整数，我可以解决问题。

例：1。二进制搜索，这里我只需要 return 1 如果找到，否则 -1.

例：2。一个数组中的最大数，只需要return一个数字。

但是当涉及到 return 数组时，比如当我们需要整个数组作为输出时（例如：排序）。

我觉得很难

任何人都可以提供最佳方法吗？

下面是我的二进制搜索方法。

#include<stdio.h>
char* Divide(int arr[],int l,int r,int key)
{
    int m=(l+r)/2;
    if(l==r)
    {
        if(key==arr[m])
            return "Found";
        else
            return "Not Found";
    }
    else
    {
        if(key==arr[m])
            return "Found";
        else if(key>arr[m])
            Divide(arr,m+1,r,key);
        else
            Divide(arr,l,m,key);
    }
}
int main()
{
    int arr[]={1,2,3,4,5,6,7,8};
    int n=sizeof(arr)/sizeof(arr[0]);
    char* result=Divide(arr,0,n-1,10);
    printf("%s\n",result);
    return 0;
}

Answer 1

您必须 return 递归调用中的值尝试

#include<stdio.h>
char* Divide(int arr[],int l,int r,int key)
{
    int m=(l+r)/2;
    if(l==r)
    {
        if(key==arr[m])
            return "Found";
        else
            return "Not Found";
    }
    else
    {
        if(key==arr[m])
            return "Found";
        else if(key>arr[m])
            return Divide(arr,m+1,r,key); // just returning values here
        else
            return Divide(arr,l,m,key); // and here would make it work
    }
}
int main()
{
    int arr[]={1,2,3,4,5,6,7,8};
    int n=sizeof(arr)/sizeof(arr[0]);
    char* result=Divide(arr,0,n-1,10);
    printf("%s\n",result);
    return 0;
}

在 online compiler

查看演示

分而治之——返回一个数组

Divide and Conquer-Returning an array

c

arrays

sorting

algorithm

divide-and-conquer