# Help Needed Asap With Searching An Array!

• 05-22-2003
HelpMe++
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.

• 05-22-2003
quzah
Quote:

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.
• 05-22-2003
HelpMe++
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.
• 05-22-2003
quzah
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.
• 05-22-2003
R.Stiltskin
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.
• 05-23-2003
CornedBee
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.