array search complexity problem

This is a discussion on array search complexity problem within the C Programming forums, part of the General Programming Boards category; find the commom numbers in two integer arrays with minimum code using c programming and explain its complexity.......

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    2

    Angry array search complexity problem

    find the commom numbers in two integer arrays with minimum code using c programming and explain its complexity....
    Last edited by vnbp8187; 02-24-2011 at 10:57 AM.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Please do your own homework.

    Make an attempt... get it as far along as you can... then If you get stuck post your code (In code tags please) and we'll see what we can do...

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    29
    Though CommonTater is correct.. noone will write it for you. (Or shouldn't)..

    I suggest running a while loop, with x and y as the components. Y will increase till the end of the array. If there is a common number it'll say so. Then x increases by 1 when y is max, and set y back to 0.

    It'll look all the way around, and should work. There's other methods. But that'll be basic, and no code overload.
    Last edited by Crosility; 02-24-2011 at 10:15 AM.

  4. #4
    Registered User
    Join Date
    Feb 2011
    Posts
    2
    This is my code but i want it to be more short , "only 1 if loop" .and how can i caliculate the complexity of this program???please help me...


    #include<stdio.h>
    /* Function prints common of a1[] and a2[] */
    int common(int a1[], int a2[], int m, int n) /* m is the size in a1[] n is the size in a2[] */
    {
    int i = 0, j = 0;
    while(i < m && j < n)
    {
    if(a1[i] < a2[j])
    i++;
    else if(a2[j] < a1[i])
    j++;
    else /* if a1[i] == a2[j] */
    {
    printf(" %d ", a2[j++]);
    i++;
    }
    }
    }

    /* program to test above function */
    int main()
    {
    int a1[] = {1, 2, 4, 5, 6};
    int a2[] = {2, 3, 5, 7};
    int m = sizeof(a1)/sizeof(a1[0]);
    int n = sizeof(a2)/sizeof(a2[0]);
    common(a1, a2, m, n);
    getchar();
    return 0;
    }

    Output:2 5

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,555
    Here's your code with code tags and proper indentation (please do this yourself in the future).
    Code:
    #include<stdio.h>
    /* Function prints common of a1[] and a2[] */
    int common(int a1[], int a2[], int m, int n) /* m is the size in a1[] n is the size in a2[] */
    {
        int i = 0, j = 0;
        while(i < m && j < n)
        {
            if(a1[i] < a2[j])
                i++;
            else if(a2[j] < a1[i])
                j++;
            else /* if a1[i] == a2[j] */
            {
                printf(" %d ", a2[j++]);
                i++;
            }
        }
    }
    
    /* program to test above function */
    int main()
    {
        int a1[] = {1, 2, 4, 5, 6};
        int a2[] = {2, 3, 5, 7};
        int m = sizeof(a1)/sizeof(a1[0]);
        int n = sizeof(a2)/sizeof(a2[0]);
        common(a1, a2, m, n);
        getchar();
        return 0;
    }
    Now, there's no such this as an 'if loop', but you can do this with one for/while loop, as you have shown, but only if the lists are sorted.

    For complexity, read up on big O notation, then take a guess at how long your program takes to run. Hint, if you make the lists twice as long, how much longer will your program take to run? What if you make the lists 10 times as long?

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    You figured out how to write this complex function and you can't optimize it or calculate its complexity? I then doubt that's your code at all. Therefore, there's no point at helping you!
    Devoted my life to programming...

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    It's not that complex - it's broken, actually.

    Try these numbers to see why.

    Code:
    /* program to test above function */
    int main()
    {
    int a1[] = {3,1,2, 4, 6, 5};
    int a2[] = {2, 3, 5, 7};
    int m = sizeof(a1)/sizeof(a1[0]);
    int n = sizeof(a2)/sizeof(a2[0]);
    printf("\n\n");
    common(a1, a2, m, n);
    getchar();
    return 0;
    }
    The better answer is to use "counting sort" on these numbers. So make an int array of 8 in SIZE, and then a while loop to "walk" through both arrays, at the same time.

    a2[] makes array[] look like this:
    Code:
    0 1 2 3 4 5 6 7
    ================
    0 0 1 1 0 1 0 1
    Because there was one 2, one 3, one 5, and one 7, in a2[].

    Repeat the above with a1[]: (in the same loop), and get the results for both summed up:

    Code:
    0 1 2 3 4 5 6 7
    ================
    0 1 2 2 1 2 1 1
    Now the shared numbers are the one's with 2 in the array[] value. Only works when each array has unique numbers, otherwise you need to use two such arrays, and the elements with the same index number, that have 1 or more in them, are your common numbers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 03-02-2011, 06:35 PM
  2. Sorting array problem :)
    By BEST in forum C++ Programming
    Replies: 7
    Last Post: 12-11-2009, 12:57 PM
  3. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  4. search array?
    By MKashlev in forum C++ Programming
    Replies: 1
    Last Post: 08-09-2002, 11:47 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21