Thread: Help Needed Asap With Searching An Array!

  1. #1
    HelpMe++
    Guest

    Help Needed Asap With Searching An Array!

    Hi, I need help asap. The problem I am having is trying to search an array of 2,000,000 long Numbers. I have populated the array with random numbers and sorted the numbers in ascending order.
    That I know how to do. What I don't know how to do is how to ask the user to enter a number, search the array for that number, and if the number is not found, re-populate the array with random numbers and search again. Do this until the number is found and output number to screen.
    I have been trying to figure out how to do a search for 4 hours now, all I have come up with is a headache and 4 hours wasted. Here is the code that I have:

    __________________________________________________ __

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




    void swap(long &val1, long &val2)
    {
    long temp;
    temp=val1;
    val1=val2;
    val2=temp;
    }

    long splitList(long longArray[], long start, long stop)
    {
    long midValue, midPoint, mid, x;
    mid=(start+stop)/2;
    swap(longArray[start], longArray[mid]);
    midPoint=start;
    midValue=longArray[start];
    for(x=start+1; x<=stop; ++x)
    if (longArray[x]<midValue)
    {
    ++midPoint;
    swap(longArray[midPoint], longArray[x]);
    }
    swap(longArray[start], longArray[midPoint]);
    return(midPoint);
    }


    void sort(long longArray[], int start, int stop)
    {
    int midPoint;
    if(start<stop)
    {
    midPoint=splitList(longArray, start, stop);
    sort(longArray, start, midPoint-1);
    sort(longArray, midPoint+1, stop);
    }
    }

    int main()
    {
    const long arraySize = 2000000; //define array size
    long longArray[arraySize]; //declare array
    int x =0;
    int rr = rand();
    srand(time(NULL)); //creates a random seed using system clock

    for (int i = 0; i < arraySize; i++)
    {

    longArray[i]=(rand()/rr*rand()/rr); //populates array with random numbers


    sort(longArray,0,arraySize-1);
    }




    {

    long size;
    long value;
    cout<<longArray[1]<<endl;
    cout<<longArray[2]<<endl;
    cout<<"Which number do you want to search for?"<<endl;
    cin>>value;
    {
    int scan=0;
    while ((scan<size) && (longArray[scan]!=value))
    scan++;
    if (scan<size)

    cout<<scan;
    else
    main();
    }



    }
    }
    __________________________________________________ __

    I know the code is a mess at the moment, I will be cleaning it up, but this is what I have so far. The search that I have implemented is not producing the correct results. Can someone "fix" my search code and tell me why it is not producing the correct results? As you can see in the "COUT" statements in the main, I was outputting elements 1 and 2 so that I could search for those exact numbers. The thing is. I don't think my random number generator is working correctly either, since elements 1 and 2 are negative, and the rest of the elements are zero. I would REALLY appreciate some help.

    THanks in advance

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    That I know how to do. What I don't know how to do is how to ask the user to enter a number, search the array for that number, and if the number is not found, re-populate the array with random numbers and search again. Do this until the number is found and output number to screen.
    So you have a list of two million numbers? Whatever for?

    Anyway, when you begin searching, the list is sorted right? This is trivial then. You can do a binary search if you like, or you can just do it sequentially.
    Code:
    for( x = 0; x < arraySize; x++ )
        if( array[x] == somevalue )
            break or return array[x];
    repopulate_array( );
    A binary search you just pick a starting point, and if that slot is less than the number, you jump ahead half the size, if it's lower, you jump down way. Repeat until you find it, or until there is no more space to jump.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    HelpMe++
    Guest
    Thanks for the help on the search.

    What about the random numbers, any idea what it is I am doing wrong? It is not populating the array correctly. Most of the elements end up being zero.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    longArray[i]=(rand()/rr*rand()/rr);
    Why the complexity? (Yeah I know, to try and get a better random number.) This is likely your problem however.

    x = r() / N * r() / N;
    x = r() / (N* r()) / N;
    x = r() / Y / N;
    x = (r()/Y) / N;
    x = Z / N;

    See how it works? Order of presidence. I believe that's what you're ending up with. That's why you end up with most as zero. You'll want to add some parenthesis so that works better:

    x = ( r() / N ) * ( r() / N );

    Or better yet:

    x = ( r() % r() ) * ( r() % r() );

    But anyway, the reason you're ending up with a bunch of zeros is likely due to the multiple division operations that occur.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    Take the sort call out of the loop that is trying to fill the array. You keep sorting junk from uninitialized elements that's replacing the values as you load them (aside from the fact that you are sorting the array 2000000 times).

    By the way, I don't think the divide, mult, divide is a problem. It works fine for me. Mult & divide have equal precedence, so should just be executed sequentially from left to right. I believe that is standard. (I just tested it with DevC++ and MSVC 6.0 & it definitely works that way with both, and neither gave any problem with the arithmetic you are doing.
    Last edited by R.Stiltskin; 05-22-2003 at 05:52 PM.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Combining a million pseudo-random numbers doesn't make it more random. Have one rand() call for each number, it saves time.


    And use an STL set for this. Big advantage: sorting is done automatically.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Queens, problem with searching 2D array
    By Sentral in forum C++ Programming
    Replies: 35
    Last Post: 03-11-2009, 04:12 PM
  2. Searching between array indicies
    By Asagohan in forum C Programming
    Replies: 7
    Last Post: 04-27-2005, 12:28 AM
  3. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  4. Searching for multiple items in an array
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 12-04-2001, 03:26 PM
  5. Structure Array searching
    By ling in forum C Programming
    Replies: 4
    Last Post: 10-18-2001, 12:39 PM