As you will solve more complex problems, you will find that searching for values
ID: 3788757 • Letter: A
Question
As you will solve more complex problems, you will find that searching for values in arraysbecomes a crucial operation. In this part of the lab, you will input an array from the user,along with a value to search for. Your job is to write a C++ program that will look for thevalue, using the linear (sequential) search algorithm. In addition, you should show howmany steps it took to find (or not find) the value, and indicate whether this was a best orworst case scenario (… remember the lecture). You may refer to the pseudo-code in thelecture, but remember that the details of the output and error conditions are not specifiedthere. Also, note that in pseudo-code arrays are sometimes defined with indices 1 to N,whereas in C++ the indexes span from 0 to N-1.
The program will work as follows. First, you should ask the user to enter the size of thearray, by outputting:
“Enter the size of the array: ”
to the console. If the user enters an incorrect size, you should output the error message:
“ERROR: you entered an incorrect value for the array size!”
and exit the program. If the input is a valid size for the array, ask the user to enter thedata, by outputting
“Enter the numbers in the array, separated by a space, and press enter: ”
Let the user enter the numbers of the array and store them into a C++ array. Up to now,this should be exactly the same code as Lab#2. Next, ask the user a value v to search forin the array (called the “key”), by outputting:
“Enter a number to search for in the array: ”
to the screen, and read the key v.
Search for v by using the linear search algorithm. If your program finds the key, youshould output:
“Found value v at index i, which took x checks.”
where i is the index of the array where v is found, and x is the number of searchoperations taken place. Hint: i and x are not the same, think about the starting value of iand starting value of x.
If you doesn’t find the key, then output:
“The value v was not found in the array!”
Then indicate whether you happened to run into a best or worst case scenario. In case youdid, output:
“We ran into the best case scenario!”
or
“We ran into the worst case scenario!”
otherwise, don’t output anything.
Example runs (input is in italic and bold):
Enter the size of the array: 5
Enter the numbers in the array, separated by a space, and press enter: 1 5 9 7 3
Enter a number to search for in the array: 9
Found value 9 at index 2 which took 3 checks.
Enter the size of the array: -5
ERROR: you entered an incorrect value for the array size!
Enter the size of the array: 5
Enter the numbers in the array, separated by a space, and press enter: 9 5 1 7 3
Enter a number to search for in the array: 9
Found value 9 at index 0 which took 1 checks.
We ran into the best case scenario!
Enter the size of the array: 5
Enter the numbers in the array, separated by a space, and press enter: 4 5 6 8 2
Enter a number to search for in the array: 2
Found value 2 at index 4 which took 5 checks.
We ran into the worst case scenario!
Explanation / Answer
/**
C++ program that prompt user to enter size and number of elements in array.
Then prompt user to enter search key and finds the element in the array
then print the index or location of element and number of searches it takes
to find element.
*/
//lsearch.cpp
#include<iostream>
using namespace std;
int main()
{
int *arr;
int size;
int key;
bool found=false;
int posIndex=-1;
int checks=0;
//repeat until user enters a valid size
do
{
cout<<"Enter the size of the array: ";
cin>>size;
if(size<0)
cout<<"ERROR: you entered an incorrect value for the array size!"<<endl;
}while(size<0);
//create an dynamic array of size
arr=new int[size];
//read input values from user
cout<<"Enter the numbers in the array, separated by a space, and press enter: ";
for(int i=0;i<size;i++)
cin>>arr[i];
//prompt for key to search
cout<<"Enter a number to search for in the array:";
cin>>key;
//linear search to find a key
for(int i=0;arr[i]!='' &&!found;i++)
if(arr[i]==key)
{
posIndex=i;
checks++;
found=true;
}
//check if value is found
if(found)
{
cout<<"Found value "<<key<<" at index "<<posIndex+1<<" which took "<<checks<<" checks."<<endl;
if(checks<size/2)
cout<<"We ran into the best case scenario!"<<endl;
else
cout<<"We ran into the worst case scenario!"<<endl;
}
else
cout<<"value not found"<<endl;
//pause program output on console.
system("pause");
return 0;
}
sample output:
Enter the size of the array: 5
Enter the numbers in the array, separated by a space, and press enter: 1 2 3 4 5
Enter a number to search for in the array:2
Found value 2 at index 2 which took 1 checks.
We ran into the best case scenario!
Press any key to continue . . .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.