Search and display the comparison

[msherindil]

I need help with the following question, I don't want the whole code but I really need help with this section. (DISPLAY THE NUMBER OF KEY COMPARISON FOR EACH SEARCH). Here is the question.

Method 1A
1A-1. Create one array arr1 of size 1000. Populate it with random numbers in the range from 0 to 2000.
1A-2. Randomly generate 5 numbers and try to search each number in the array.
1A-3. Display the number of key comparison for each search.
1A-4. Display a table like the following:


Target Number # of key comparison
356 (Not Found) 1000

54 256

1568 546

349 (not found) 1000

545 678

Average 696

[jonnin]

just count.

lets say you do a brute force search:

for(dx = 0; dx < maxsize; dx++)
{
if(array[dx] == searchval)
break;
}

cout << "found it at " << dx << "taking " << dx <<"comparisons" ;

if you had a more complex search algorithm, you would maintain a separate count variable and increment it every time you compare. Here, because the index and the count are the same, I didn't need the extra variable.

[icy1]

DISPLAY THE NUMBER OF KEY COMPARISON FOR EACH SEARCH

Yeah, this is slightly weird phrasing for an array, but likely he wants you to code it as jonnin said.

For an unsorted array, you need to check the probe against every element until you find what you're looking for, or not at all. For each of the five generated numbers, you'd loop through the whole array, making up to 1000 comparisons to check if number matches what's in there.

Likely you want a bool variable named "found" or so, so that on match you can set it to true before breaking. At end of that loop, if !found, you can say so and output the array size. For the case of success, you can either remember the last index checked and output that (+1), or keep a count.

[msherindil]

Thank you guys.
This is my code I still need to display target numbers and number of key comparison like a table. I figured out to generate random numbers only.

#include <iostream>
#include <ctime>

using namespace std;

int linearSearch(int [], int, int);
void comparison(int [], int);
const int Size = 1000;

int main()
{
int arr1[Size];
srand(time(NULL));

for (int i = 0; i < 1000; i++)
{
if (i == 0)
arr1[i] = 1000;
else
arr1[i] = rand()%2000 + 1;
}

for (int count = 0; count < 5; count++)
{
int index = 0;
int random;

random = rand()%2000 + 1;
cout << "random generated # " << random << endl;

index = linearSearch(arr1, Size, random);
if (index == -1)
{
cout << "The index randam # " << random << " is not in the array. " << endl;
}
else
cout << "The index randam # " << random << " is " << index << endl;
}

cout << "Target Number " << " " << " # of Key Comparison " << endl;


return 0;
}

/// ******************************************************.

int linearSearch(int arr[], int len, int random)
{
int index = 0;
int position = -1;
bool found = false;

while(index < len && !found)
{
if (arr[index] == random)
{
found = random;
position = index;
return position;

}
index++;
}
return position;

}

///*****************************************************8

void comparison(int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";

}

[jonnin]

so, you need to count them and get the answer back.

int linearSearch(int arr[], int len, int random, int &compcount)
{
int index = 0;
int position = -1;
bool found = false;
compcount = 0;

while(index < len && !found)
{
if (arr[index] == random)
{
compcount++;

and in main, call it with the extra variable:
index = linearSearch(arr1, Size, random, somecountvariable);

and then just print it.

[msherindil]

appreciate that.
I implemented this code but still I am getting some errors like ( /// error: expected primary-expression before '}' token at the closing bracket of while loop in function) or (undefined reference to linearSearch(int, int, int, int).'

I need alittle more codes regarding this, I don't know may be I missed in main function couldn't print it the right way.

[jonnin]

error 1 is just a syntax error. show me the code. it is most likely a missing ;

error 2 sounds like you updated the function header but not the prototype, or the reverse. This is an example of the error:

void foo(int x, int y);

main()
{
   foo(x,y,z); //error, it has only seen a 2 variable version of the function!
}

void foo(int x, int y, int z)
{
     ;
}

[msherindil]

Thank you for your help.
I fixed the syntax error, but it doesn't give me what I want.

this is the question
Method 1A
1A-1. Create one array arr1 of size 1000. Populate it with random numbers in the range from 0 to 2000.
1A-2. Randomly generate 5 numbers and try to search each number in the array.
1A-3. Display the number of key comparison for each search.
1A-4. Display a table like the following:

and here is my codes.

#include <iostream>
#include <ctime>

using namespace std;

int linearSearch(int [], int, int, int &);
void comparison(int [], int);
void showArray(int [], int);
const int Size = 10;

int main()
{
int arr1[Size];

srand (time(NULL));
for (int i = 0; i < Size; i++)
{
arr1[i] = rand()%2000 + 1;
}

for (int i = 0; i < Size; i++)
{
cout << "Array1 Random generated # " << arr1[i] << endl;

}
cout << endl;

int index = 0;
int random;
int comp;
index = linearSearch(arr1, Size, random, comp);
showArray(arr1, Size);


return 0;
}

/// ******************************************************.

int linearSearch(int arr[], int len, int random, int &compcount)
{
int index = 0;
int position = -1;
bool found = false;
compcount = 0;

while(index < len && !found)
{
if (arr[index] == random)
{
found = true;
position = index;
}
compcount++;
}
return position;

}

///*****************************************************
void showArray(int array[], int size)
{
cout << "Target #" << " " << " key comparison " << endl;
for (int count = 0; count < size; count++)
cout << array[count] << " ";
}


///***************************************************8

void comparison(int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";
}

[jonnin]

hang on. at a guess, its off by one because it forgets to count when it finds it.
but im going to run what you have a bit.

int random: uninitialized then used in the function.

you never print your values. I would think that show-array needs to get comp from main passed into it, or main should print comp, or something?


the while loop does not appear to terminate as index NEVER CHANGES in the loop. I think you missed an index++ in there;

[jonnin]

I made these crude changes to illustrate. Its probably not 100% what you want but its more or less working now. see lines 31, 36, 57. I was wrong about the off by one, its ok.

#include <iostream>
#include <ctime>

using namespace std;

int linearSearch(int [], int, int, int &);
void comparison(int [], int);
void showArray(int [], int);
const int Size = 10;

int main()
{
int arr1[Size];

srand (time(NULL));
for (int i = 0; i < Size; i++)
{
arr1[i] = rand()%2000 + 1;
}

for (int i = 0; i < Size; i++)
{
cout << "Array1 Random generated # " << arr1[i] << endl;

}
cout << endl;

int index = 0;
int random;
cin >> random;
int comp;
index = linearSearch(arr1, Size, random, comp);
showArray(arr1, Size);

cout <<endl << "comparisons = " << comp << endl;
return 0;
}

/// ******************************************************.

int linearSearch(int arr[], int len, int random, int &compcount)
{
int index = 0;
int position = -1;
bool found = false;
compcount = 0;

while(index < len && !found)
{
if (arr[index] == random)
{
found = true;
position = index;
}
compcount++;
index ++;
}
return position;

}

///*****************************************************
void showArray(int array[], int size)
{
cout << "Target #" << " " << " key comparison " << endl;
for (int count = 0; count < size; count++)
cout << array[count] << " ";
}


///***************************************************8

void comparison(int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";
}

[msherindil]

thanks
this code runs exactly like the one you sent you, I know you added a couple lines but still the output is the same as mine. Any way appreciate your help.

[msherindil]

I made some changes to my code but how do you display the table I want.
for example
target numbers # of key comparison

this is my code
#include <iostream>
#include <ctime>

using namespace std;

int linearSearch(const int [], int, int);
const int Size = 1000;

int main()
{
int arr1[Size];
int index = 0;
int target = -1;

srand (time(NULL));
for (int i = 0; i < Size; i++)
{
arr1[i] = rand()%2000 + 1;
}

for (int i = 0; i < 5; i++)
{
cout << "Random generated # " << arr1[i] << endl;

}

cout << endl;

index = 0;
target = 250;

index = linearSearch(arr1, Size, target);

/// show the result of the search
/// if linear search returned -1, then the target is not in the array

if (index == -1)
{
cout << "The Target #: " << target << " is not in the array. " << endl;
}
else
{
cout << "The Target #: " << target << " is " << index << endl;
}


index = 0;
target = 500;

index = linearSearch(arr1, Size, target);


/// show the result of the search
/// if linear search returned -1, then the target is not in the array

if (index == -1)
{
cout << "The Target #: " << target << " is not in the array. " << endl;
}
else
cout << "The Target #: " << target << " is " << index << endl;

index = 0;
target = 980;

index = linearSearch(arr1, Size, target);


/// show the result of the search
/// if linear search returned -1, then the target is not in the array

if (index == -1)
{
cout << "The Target #: " << target << " is not in the array. " << endl;
}
else
cout << "The Target #: " << target << " is " << index << endl;

index = 0;
target = 869;

index = linearSearch(arr1, Size, target);


/// show the result of the search
/// if linear search returned -1, then the target is not in the array

if (index == -1)
{
cout << "The Target #: " << target << " is not in the array. " << endl;
}
else
cout << "The Target #: " << target << " is " << index << endl;

index = 0;
target = 969;

index = linearSearch(arr1, Size, target);


/// show the result of the search
/// if linear search returned -1, then the target is not in the array

if (index == -1)
{
cout << "The Target #: " << target << " is not in the array. " << endl;
}
else
cout << "The Target #: " << target << " is " << index << endl;


return 0;
}

/// ******************************************************.

int linearSearch(const int arr[], int len, int random)
{
int index = 0;
int position = -1;
bool found = false;


while(index < len && !found)
{
if (arr[index] == random)
{
found = true;
position = index;
}
index++;
}
return position;

}

[jonnin]

I can't see what you are still asking.