Search Benchmarks
Search Benchmarks
Write a program to generate an array of 100 random three-digit integers (that is, between 99 and 1000, exclusively). The program should display the array values (formatted as columns, ten items per line).
Once the numbers are generated the user should prompted for the search item. The program should use a linear search to find the item. The program should keep track of the number of comparisons made and whether or not the item was found.
The program should then sort the array (using the sort algorithm of your choice), display the sorted array, and then repeat the search using binary search. Again, the program should report the number of comparisons made.
This program will make use of at least five functions:
void displayArray(const int theArray[], int theSize)
void randomizeArray(int theArray[], int theSize)
void sortArray(int theArray[], int theSize)
void sequentialSearch(const int theArray[], int theSize, int theSearchItem)
void binarySearch(const int theArray [], int theSize, int theSearchItem)
The two search functions have return type void, as they must provide two different pieces of information (the number of comparisons made, and whether or not the item was found). Therefore these functions will use cout statements to provide this information.
To really see the efficiency of binary search, change your array size to something much larger (a hundred thousand or so), comment out the calls to displayArray() (you don't want to see a hundred thousand numbers on the screen), and look at the number of comparisons made by these two search algorithms.
Write a program to generate an array of 100 random three-digit integers (that is, between 99 and 1000, exclusively). The program should display the array values (formatted as columns, ten items per line).
Once the numbers are generated the user should prompted for the search item. The program should use a linear search to find the item. The program should keep track of the number of comparisons made and whether or not the item was found.
The program should then sort the array (using the sort algorithm of your choice), display the sorted array, and then repeat the search using binary search. Again, the program should report the number of comparisons made.
This program will make use of at least five functions:
void displayArray(const int theArray[], int theSize)
void randomizeArray(int theArray[], int theSize)
void sortArray(int theArray[], int theSize)
void sequentialSearch(const int theArray[], int theSize, int theSearchItem)
void binarySearch(const int theArray [], int theSize, int theSearchItem)
The two search functions have return type void, as they must provide two different pieces of information (the number of comparisons made, and whether or not the item was found). Therefore these functions will use cout statements to provide this information.
To really see the efficiency of binary search, change your array size to something much larger (a hundred thousand or so), comment out the calls to displayArray() (you don't want to see a hundred thousand numbers on the screen), and look at the number of comparisons made by these two search algorithms.
Please, review the link below:
https://stackoverflow.com/help/how-to-ask
Could you be a little specific of what issues are you having?
https://stackoverflow.com/help/how-to-ask
Could you be a little specific of what issues are you having?
| i need help please. |
If my guess is right go to the job section. I am sure there are plenty of people who would do it for a few bucks.
If my guess is wrong and you want to do it for yourself then start simple.
Implement first
void randomizeArray(int theArray[], int theSize), then
void displayArray(const int theArray[], int theSize)Once they are working implement the other functions, one by one.
void displayArray(const int theArray[], int theSize);
void randomizeArray(int theArray[], int theSize);
void sortArray(int theArray[], int theSize);
void sequentialSearch(const int theArray[], int theSize, int theSearchItem);
void binarySearch(const int theArray [], int theSize, int theSearchItem);
int main()
whats next??
void randomizeArray(int theArray[], int theSize);
void sortArray(int theArray[], int theSize);
void sequentialSearch(const int theArray[], int theSize, int theSearchItem);
void binarySearch(const int theArray [], int theSize, int theSearchItem);
int main()
whats next??
the function bodies that do the work.
again, try just making an array of say 10 random values and printing that out to get started.
then do the easy linear search, see if a number is in your array. Now test that, both when the value is there and when it isnt.
FYI the problem statement is a bit misleading.
sorting the data is going to cost you at least as much as the linear search, so unless you look for more than 2 values in the data, it won't be any faster. You will start to see the power of the binary search once you look for more values and use more than 10 elements. On top of this the problem as stated can be solved without directly sorting or searching at all, with a single operation to verify if an item exists and how many times it existed in the data. To say that with examples... if you had 100 elements in the array, the act of sorting it costs you at least 100 advanced operations, and takes more time than looking at the 100 items once each to find your target. If you had 10 things to look for, looking at all 100 items 10 times is more work than sorting it first, then looking at it with the binary search. More advanced, imagine you had this
int table[1000] = {0};
for(i = 0; i < n; i++)
{
randomvalue = some code to get your value 100-999
table[randomvalue]++;
}
now search for the value 123.
is table[123] zero? if not, you have a 123 in your random data. one thing to look at.
if table[123] is 10, you had 10 repeated copies of the value 123.
No searching, no 'true' sorting (its actually sorted upon creation, by virtue of the table, at no cost of comparisons or data movement etc).
Fun times!
again, try just making an array of say 10 random values and printing that out to get started.
then do the easy linear search, see if a number is in your array. Now test that, both when the value is there and when it isnt.
FYI the problem statement is a bit misleading.
sorting the data is going to cost you at least as much as the linear search, so unless you look for more than 2 values in the data, it won't be any faster. You will start to see the power of the binary search once you look for more values and use more than 10 elements. On top of this the problem as stated can be solved without directly sorting or searching at all, with a single operation to verify if an item exists and how many times it existed in the data. To say that with examples... if you had 100 elements in the array, the act of sorting it costs you at least 100 advanced operations, and takes more time than looking at the 100 items once each to find your target. If you had 10 things to look for, looking at all 100 items 10 times is more work than sorting it first, then looking at it with the binary search. More advanced, imagine you had this
int table[1000] = {0};
for(i = 0; i < n; i++)
{
randomvalue = some code to get your value 100-999
table[randomvalue]++;
}
now search for the value 123.
is table[123] zero? if not, you have a 123 in your random data. one thing to look at.
if table[123] is 10, you had 10 repeated copies of the value 123.
No searching, no 'true' sorting (its actually sorted upon creation, by virtue of the table, at no cost of comparisons or data movement etc).
Fun times!
Last edited on
Topic archived. No new replies allowed.