C finding second largest number in an array

Question

As the title says, I have to find the second largest number in an array and if every number in that array is equal I should write that it's -∞. I wrote this, could anyone check to see if I could perhaps optimize it a little better? This array is just an example, it should be x[1...n] but since I have to rewrite it to pseudocode I took that one as an example

#include <stdio.h>
int main()
{
    int x[7]={90,90,78,41,21,27,35};
    int i, max, secmax, y;
    secmax=0;
    max=x[0];
    for(i=1;i<=7;i++)
        {
        if (x[i]>max)
            {
            secmax=max;
            max=x[i];
            }
        else if (x[i]>secmax&&x[i]<max)
                {
            secmax=x[i];
            }
        }

    for(i=0;i<7;i++)
        if(x[i]==x[i+1])
            y++;

    if (y==6)
        printf("sec max to minus nieskonczonosc \n");
    else 
        printf("max to %d a secmax to %d\n",max,secmax);
    return 0;
}

Answer 1

In my code I am replacing the largest number to zero in the array after printing it, this way we have removed the largest. Then using the new array to find the second largest number. This code is beginner friendly and easy to understand  
// Program to print second largest number
#include<stdio.h>
int main()
{
    int num[10],n,i,largest,second;
    printf("Enter n: ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter num %d: ",i+1);
        scanf("%d",&num[i]);
    }
    largest = num[0];
    for(i=1;i<n;i++)
    {
        if(largest<num[i])
         largest = num[i];
    }
    printf("The largest is %d\n",largest);
    for(i=0;i<n;i++)
    {
        if(largest == num[i])
        {
            num[i] = 0;
        }
    }
    printf("Array is: \n");
    for(i=0;i<n;i++)
    {
                                                                                                        printf("%d\t",num[i]);
    }
    second = num[0];
    for(i=1;i<n;i++)
    {
        if(second<num[i])
          second = num[i];
 
    }
    printf("The second largest is %d",second);
    return 0;
}

Answer 2

You can avoid the last scan of the whole array by setting secmax initially to negative infinity. This way it will always have the correct value.

Also, you have a bug in your code: i<=7 should be replaced with i < sizeof(x)/sizeof(x[0]). Otherwise your x[i] will give you a segfault.

Answer 3

I have made a few changes and added some comments. Discussion below the code.

#include <limits.h> // for INT_MIN macro
#include <stdio.h>
int main()
{
    // Let the compiler count length of array.
    // -- declare "x[]", no need to specify length
    const int x[] = { 90, 90, 78, 41, 21, 27, 35 };
    // -- use sizeof() math to find length of array
    // -- use const int rather than #define so debugger can see value
    const int len = sizeof(x) / sizeof(x[0]);
    int i, max, secmax, same_count;

    if (0 == len)
    {
        // zero-length list: return INT_MIN
        printf("sec max to minus nieskonczonosc: %d\n", INT_MIN);
        return 0;
    }

    secmax = max = INT_MIN;

    same_count = 0;

    // start loop at 0
    for(i = 0; i < len; ++i)
        {
        // We'll use the same idea you originally used to find if all values were
        // the same, but do it as part of the same loop.  No need to loop over
        // the values twice.  For a short list, looping twice is not a big deal,
        // but for really large data sets it will save lots of time to do it this way.
        same_count += (x[0] == x[i]);

        if (x[i]>max)
            {
            // Found value greater than current max; shift max down to secmax
            // and save new max value.
            secmax=max;
            max=x[i];
            }
        else if (x[i]>secmax && x[i]<max)
            {
            // It wasn't greater than max, but is greater than secmax.
            // Save new secmax value.
            secmax=x[i];
            }
        }

    if (len == same_count)
        printf("sec max to minus nieskonczonosc: %d\n", INT_MIN);
    else 
        printf("max to %d a secmax to %d\n",max,secmax);

    return 0;
}

There isn't much we can do to improve the run time. Your code is already doing the straightforward thing to find the desired values.

The one thing we can do that will help is to get rid of your second loop, by doing its work inside the first loop.

@Rerito's answer changed the algorithm: instead of counting how many values were identical, and seeing if the count matched the length, that answer starts with a 1 bit and uses bitwise "and" with a value comparison. If the comparison ever fails, the result of the comparison will be zero, and bitwise "and" with a value of 0 results in 0. Thus, if the comparison ever fails, the initial 1 bit is cleared to a 0 bit, and when the loop is over with, if that 1 bit is still set, then every value must have been identical.

I kept your basic algorithm of counting how many values are the same and then checking to see if the count matches the length. I renamed the counting variable because the name y is uninformative, I moved the count updating to inside the first loop (and then got rid of the second loop), and I reworked the code so that you can change the array values and it should all just work.

It's bad practice to have unconnected "magic" values sprinkled through your code. Your original code has a 7 in three places and a 6... thus laying itself open for a bug when someone changes the length of the array. My code has the C compiler count how many values are in the array, sets a constant (len), and then exclusively uses that constant. Thus, you can simply add or remove values in the array and the changed code still works correctly.

EDIT: @sds wrote this: "You can avoid the last scan of the whole array by setting secmax initially to negative infinity. This way it will always have the correct value."

Oh wow, he's right! All we have to do is set secmax to the value we want to return if every value is the same, because the code is written to only set secmax when the code sees a value that is less than max, and if every value is the same, then secmax will never change.

Answer 4

Here is what you can do :

int get_second_max(int *x, size_t n)
{
    int max[2] = {-MAX_INT,-MAX_INT};
    int i = 0, same = 1;
    if (NULL == x || 0 == n)
        return -MAX_INT;

    max[0] = x[0];
    max[1] = x[0];
    for(i = 1; i < n; i++) {
        /* same is used to check 
         * if the array contains 
         * the same number all along.
         */
        same &= (x[i] == x[i-1]);
        /* At the i-th iteration :
         * -> max[0] stores the maximum value
         * -> max[1] stores the second maximum value
         */

        /* We hit a new max value, we must :
         * 1. Update the second max value with the current max value
         * 2. Update the current max value with the new max we found
         */
        if(x[i] > max[0]) {
            max[1] = max[0];
            max[0] = x[i];
        } else if(x[i] > max[1]) {
            max[1] = x[i];
        }
    }
    if(same) {
        return -MAX_INT;
    } else {
        return max[1];
    }
}