The most basic way to find a value in an array is to successively examine every element until the value is found or the end of the array is reached. The amount of time this takes increases with the size of the array, and we would expect it to be proportional to the size of the array. This lab will test that hypothesis.
Write a program that starts by putting 2 million random values into an array. The statement
$x = rand 100;
will generate a random value between 0 and 100. Then it should search successively larger parts of the array, starting with the first 125,000 entries. To ensure that it finds the value it is looking for, it should generate a random index into the array using
int rand 125_000;
which will generate a random integer between 0 and 124,999 inclusive, then use this index to get the value from the array. It should then enter a loop that searches successive positions in the array, starting at 0 until it finds the value. To find out how long the search took, use the statement:
$start = times();
before the search starts, and
$end = times();
then the difference, $end - $start, will be the number of seconds
that elapsed between the two calls. You should repeat this search at least five
times, searching for values at different random locations within the first 125,000
positions, and average the times. It should then search 250,000 entries, then
500,000, doubling until it reaches two million, averaging over at least five
tests each time. If the running time is really proportional to the number of
values searched, the averages should go up by about a factor of two each time.