1. If a linear search function is searching for a value that is stored in the last element of a 10,200-element array, how many comparisons will the search function have to make to locate the value?

2. Given an array of 824 elements, what is the average number of comparisons a linear search function will make to locate a specific value?

3. Assume that a binary search function is searching for a value that is stored in the middle element of an array. How many times will the function read and compare elements in the array before it finds the value?

4. What is the maximum number of comparisons that a binary search function will make when searching for a value in an array that contains 2,048 elements? (Be careful, the book does not go far enough in using powers of 2 to explain the maximum numbers of comparisons needed. Especially in the case where the search value is not in the array.)

5. Why is a binary search function almost always more efficient than a linear search function? Make you explanation complete, concise, and specific. (you may even find a good explanation in our textbook.)

Programming Exercise (50 points):

Use the file named USPopulation.txt that is available for download in the Blackboard course to provide answers to this Programming Exercise.

The file named USPopulation.txt contains the midyear population of the United States, in thousands, during the years 1950 through 1990. The first line in the file contains the midyear population for 1950, the second line contains the midyear population for 1951, and so forth.

Write a C++ program that reads the contents of the file into an array. The program will then determine and display the following information:

• The average annual change in population during the period from 1950 through 1990.
• The year with the greatest increase in population during the period from 1950 through 1990.
• The year with the smallest increase in population during the period from 1950 through 1990.