As you will solve more complex problems, you will find that searching for values in arrays becomes 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 the value, using the linear (sequential) search algorithm. In addition, you should show how many steps it took to find (or not find) the value, and indicate whether this was a best or worst case scenario (... remember the lecture). You may refer to the pseudo-code in the lecture, but remember that the details of the output and error conditions are not specified there. 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 the array, 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 the data, 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 for in 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, you should 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 search operations taken place.
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 you did, output: "
We ran into the best case scenario!" or "We ran into the worst case scenario!"
otherwise, don't output anything.