Introduction
c，c，，for，sort，
c
Requirement
Due in your lab section.
You will be empirically comparing the efficiency of linear search
and binary search:
• Implement the code for both search functions (the code is in
the textbook - test them to make sure you entered them
correctly).
• Modify them both to count the number of comparisons
made during the search and print out the final count.
In your main function:
• Declare integer arrays of sizes 1,000, 10,000, 100,000 and
1,000,000 (one array of each size).
• Fill the arrays with random integers in the range one to a
million (random numbers are covered in chapter 3, if you
need a review).
• Sort the arrays (remember that binary search requires a
sorted array). I give an example below of using the built-in
sort function.
• Call the linear search and binary search for each array, with
a randomly chosen target value in the range one to a million
(use the same target for both the linear and binary searches
for a particular array).
When you run your program, you should be able to see how
many comparisons it took both algorithms to run on different
problem sizes. This lets you concretely compare for linear and
binary search how the time required changes as the size of the
problem changes.
Array sorting example:
#include
int main()
{
int array[] = {23, 5, -10, 0, 0, 321, 1, 2, 99, 30};
int size = 10;
std::sort(array, array + size);
for (int i = 0; i < size; i++)
std::cout << array[i] << ‘ ‘;
}
This program first initializes an array of ints. Next we use the
built in sort function, which requires that you include
. It takes two arguments - a pointer to the first
element, and a pointer to the final element (arrived at here
through pointer arithmetic). Afterward, when the array is printed
out, the elements will be in ascending numeric order.