I am trying to write a C program to find the median of an array, but the task requires to not sort the array. The current code I have works, but fails when there is a repeated number. I am struggling to find a way to account for this case. Any help would be appreciated.

#include <stdio.h>
#include <stdlib.h>

int median_finder(int size, int* data) {
    int n1, n2;
    int count = 0;
    for (int t = 0; t < size; t   ) {
    int piv = data[t];
    int higher = 0;
    int lower = 0;
    int median;
    
    if (size % 2 != 0) {
        for (int j = 0; j < size; j  ) {
            if (piv < data[j]) {
                higher  ;
            } else if (piv > data[j]) {
                lower  ;
            } 
        }
        if (higher != 0 && lower == higher) {
            printf("MEDIAN: %d\n", piv);
            return 0;
        }
    } else {
        //int num = 0;
        for (int j = 0; j < size; j  ) {
            if (piv < data[j]) {
                higher  ;
            } else if (piv > data[j]) {
                lower  ;
            } 
        }
        if (higher != 0 && (lower == size/2 || higher == size/2)) {
        
        count  ;
        if (count == 1) {
            n1 = piv;
        } if (count == 2) {
            n2 = piv;
        }

        }
    } if (count == 2) {
        if (n1 > n2) {
            median = n2;
        } else {
            median = n1;
        }
        printf("Median: %d\n", median);
        return 0;
    }
    }
}

int main(int argc, char** argv) {
    int size = atoi(argv[1]);
    argv  ;
    argv  ;
    int data[size];
    for (int i = 0; i < size; i  ) {
        data[i] = atoi(argv[i]);
    }
    median_finder(size, data);
}

CodePudding user response：

The median for an unsorted array with possible duplicate values a of length n is the element with the value a[i] where half of the remaining elements (n-1)/2 (rounded down) are between less than (lt) or less than and equal (lt eq) to a[i]:

#include <assert.h>
#include <stdio.h>

int median(size_t n, int *a) {
    assert(n > 0);
    for(size_t i = 0; i < n; i  ) {
        size_t lt = 0;
        size_t eq = 0;
        for(size_t j = 0; j < n; j  ) {
            if(i == j) continue;
            if(a[j] < a[i]) lt  ;
            else if(a[j] == a[i]) eq  ;
        }
        if((n-1)/2 >= lt && (n-1)/2 <= lt   eq)
            return a[i];
    }
    assert(!"BUG");
}

// tap-like
void test(size_t test, int got, int expected) {
    printf("%sok %zu\n", got == expected ? "" : "not ", test);
    if(got != expected) {
        printf("  --\n"
               "  got: %d\n"
               "  expected: %d\n"
               "  ...\n", got, expected);
    }
}

int main(void) {
    struct {
        size_t n;
        int *a;
    } tests[] = {
        {1, (int []) {0}},
        {2, (int []) {0, 1}},
        {3, (int []) {-1, 0, 1}},
        {4, (int []) {-1, 0, 0, 1}},
    };
    for(int i = 0; i < sizeof tests / sizeof *tests; i  ) {
        test(i 1, median(tests[i].n, tests[i].a), 0);
    }
}

CodePudding user response：

Mr or Mrs. Roo4ma, you first need to find the size. Let's say the size is odd, and your array is [2,7,3,5,9]. Then as you can see, the median is 5. which is (size 1/2). You need to find the size/2'th element if the array size is even. For that, you can use "nested for" loops. An example:

#include<stdio.h>
#include<stdlib.h>
#define size 5
int main()
{
    int a[]={2,7,3,5,9},i,j,value;
    float median;
    for(i=0;i<size;i  ){
        value=0;
        for(j=0;j<size;j  ){
            if(a[j]>a[i])
                value  ;
        }
        if(value==(size/2)){
            median=a[i];
            break;
        }
    }
    printf("Median is %.1f",median);
    return 0;
}

But if the array size is even, we must adjust. An example is :

#include<stdio.h>
#include<stdlib.h>
#define size 6
int main()
{
    int a[]={2,3,7,3,5,9,8},i,j,value;
    float median;
    for(i=0;i<size;i  ){
        value=0;
        for(j=0;j<size;j  ){
            if(a[j]>a[i])
                value  ;
        }
        if(value==((size/2)-1) || value==(size/2)){
            median =a[i];
        }
    }
    median/=2;
    printf("Median is %.1f",median);
    return 0;
}

However, unfortunately, if the user enters the same numbers, there will be some errors in my second code. And I couldn't think of a way to solve this without sorting them first.