当我 运行 这个搜索算法时空白输出屏幕

Question

我一直在练习中值搜索算法，这就是我写的-

#include <iostream>
#include <stdlib.h>

using namespace std;

int S1[10] = { 0 };
int S2[1]  = { 0 };
int S3[10] = { 0 };

int mediansearch(int A[], int k, int size)
{
    int ran = rand() % size;
    int i = 0;
    int a = 0;
    int b = 0;
    int c = 0;

    for (i = 0; i < size; i++)
    {
        if (A[ran] > A[i])
        {
            S1[a] = A[i];
            a++;
        }
        else if (A[ran] == A[i])
        {
            S2[b] = A[i];
            b++;
        }
        else
        {
            S3[c] = A[i];
            c++;
        }
    }

    if (a <= k)
    {
        return mediansearch(S1, k, a);
    }
    else if (a + b <= k)
    {
        return A[ran];
    }
    else
    {
        return mediansearch(S3, k - a - b, c);
    }
}

int main()
{
    int arr[] = { 6, 5, 4, 8, 99, 74, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = mediansearch(arr, 5, n);

    cout << "5th smallest is:" << x << endl;
}

我得到的输出是-

Process returned -1073741676 (0xC0000094) execution time : 1.704 s So, what am I doing wrong? Any kind of help will be appreciated.

Answer 1

此代码存在一些问题，第一个是变量命名。
我建议你以后选择更有意义的名字，因为当别人必须理解你的代码和你的想法时，好的命名是基础。

另一件事是参数的顺序违反直觉，因为与数组相关的对由您要查找的索引分隔。
我会写 int mediansearch(int A[], int size, int k)

这里比较相反，k应该是小于而不是大于等于a

if (a <= k) // (k < a)
{
    return mediansearch(S1, k, a);
}
else if (a + b <= k) // (k < a + b)
{
    return A[ran];
}
else
{
    return mediansearch(S3, k - a - b, c);
}

另一件事是您在所有递归调用中共享 S1、S2 和 S3，这导致了一些我无法识别的错误，也许有人发表评论会帮助我。

但是，我建议您阅读这篇文章，它详细解释了您尝试实施的过程：https://rcoh.me/posts/linear-time-median-finding/
它是 python，但它可以很容易地移植到 C/C++，事实上我就是这样做的。

#include <iostream>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

using namespace std;

int medianSearch(int A[], int size, int k)
{
    int *lows = (int *)calloc(size, sizeof(int));
    int  lowsLen = 0;

    int *highs = (int *)calloc(size, sizeof(int));
    int  highsLen = 0;

    int *pivots = (int *)calloc(size, sizeof(int));
    int  pivotsLen = 0;

    int  median;
    int  pivot;
    int  i;

    if (size == 1)
        return A[0];

    // Other ways of randomly picking a pivot
    // pivot = 0;
    // pivot = size-1;
    // pivot = size/2;

    assert(size > 0);
    pivot = rand() % size;

    for (i = 0; i < size; ++i)
    {
        if (A[i] < A[pivot])
        {
            lows[lowsLen] = A[i];
            lowsLen++;
        }
        else if (A[i] > A[pivot])
        {
            highs[highsLen] = A[i];
            highsLen++;
        }
        else
        {
            pivots[pivotsLen] = A[i];
            pivotsLen++;
        }
    }

    if (k < lowsLen)
        median = medianSearch(lows, lowsLen, k);
    else if (k < lowsLen + pivotsLen)
        median = A[pivot];
    else
        median = medianSearch(highs, highsLen, k - lowsLen - pivotsLen);

    free(lows);
    free(highs);
    free(pivots);

    return median;
}

int compare(const void *a, const void *b)
{
    return ( *(int *)a - *(int *)b );
}

int medianSorted(int A[], int size, int k)
{
    qsort(A, size, sizeof(int), compare);

    return A[k];
}

#define N 1000

int main()
{
    int arr[N];
    int brr[N];
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 200;
    int x;
    int y;
    
    for (int i = 0; i < n; ++i)
        arr[i] = brr[i] = rand();
    
    x = medianSearch(arr, n, (k-1)%n);
    y = medianSorted(brr, n, (k-1)%n);
    
    string suffix;

    switch (k % 10)
    {
        case 1: suffix = "st"; break;
        case 2: suffix = "nd"; break;
        case 3: suffix = "rd"; break;
        case 4:
        case 5:
        case 6:
        case 7:
        case 8:
        case 9:
        case 0: suffix = "th"; break;
    }
    cout << k << suffix << " smallest is: " << x << endl;
    cout << k << suffix << " smallest is: " << y << endl;
}

https://onlinegdb.com/HJc2V6Lbu