The goal for this exercise is to measure the performance of linear search. The longer-term goal is to compare this performance to other, alternative algorithms (such as binary search) so that will have a clear understanding of why the Big O notation is useful.
What you need to do to prepare for this exercise:
For this exercise, you'll be adding some simple instrumentation (extra code) to your linear search, so that it will allow you to take some simple measurements – namely, how many times your code compares an element of the array with the target value that you're looking for.
Within your SearchingAndSorting
class, copy your FindIntegerLinear
function, and rename
the copy to be FindIntegerLinearPerfMeasured
. Add to it an out
(reference) parameter
– an integer named numComparisons
. Within your FindIntegerLinearPerfMeasured
, you should
initialize (setup) the value of this parameter to be zero. Each time you compare the target (the value that you’re
looking for) to any element of the array, you should increase numComparison
’s value by one.
So if you were to search an array for something, and find it in the first slot, numComparisons
should
be 1 when the method returns. If you have an array of 20 elements, and you don't find it anywhere, numComparisons
should be 20 when the method returns.
Once you’ve done that, you should test the function (once you've written it), by adding whatever you need to add
to Main()
.
Implement the FindIntegerLinearPerfMeasured
method, within the SearchingAndSorting
class.
Note that you don't (technically) need to complete the "Linear Search" exercise in this same lesson – you can jump straight to this exercise. However, many people find it easier to do that exercise first, then copy-and-paste that code into this exercise.