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 doesnt 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, dont 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!