1. Using the template Array class (oarr9.cpp), provide member functions for:
   • linear search (this is the find routine done previously)
   • binary search (see section 5.6.2 of the text)
   • insertion sort (required by binary search, see p.138 and/or p.266)

2. Define a new Timer class to provide a general timing facility. This class should have, as member data, double-precision values for
   • ``start time'',
   • ``end time'', and
   • ``elapsed time''.
   Member functions should include methods to:
   • set the start time,
   • set the end time (and therefore to calculate the elapsed time), and
   • return the elapsed time.

   The intended use of this class is to take ``timestamps'' around code that is to be timed. So, for example, assuming there's an object tmr of class Timer, this is how it can be used:

     tmr.start();
     pos = Arrp->linsearch(seeknum);
     tmr.end();
     t_us = tmr.elapsed_us();
   		

   where t_us is a double variable which gets assigned the time that it took to do a linear search (in this case). The _us is used to signify microseconds (see below).

   Use the gettimeofday system call to obtain the current timestamp (in microseconds). The routine gettimeofday fills in a timeval structure with seconds and microseconds since the ``Unix epoch'' (January 1, 1970). Since there are a million microseconds in a second, the seconds part of timeval needs to be converted to microseconds to get the timestamp all in microseconds. Here's sample code which takes the timestamp and returns the time in microseconds:

           double          s,us,tod;
           struct timeval  tp;
   
     // get time of day (tod), return in microseconds
   
     gettimeofday(&tp,NULL);
     s = static_cast(tp.tv_sec);
     us = static_cast(tp.tv_usec);
     tod = s*1000000.0 + us;
     return(tod);
   		

   To summarize: the idea behind timer is to take timestamps before and after execution of some routine. Then taking the differnece between the end and the start time gives the amount of time spent in between the two timestamps. In this assignment, the goal is to compare the time spent executing the linear and binary search algorithms.

3. Test the running time of both search algorithms by locating the user-specified value within the list. Use input sizes ranging from 10, to 100, to 1000, to 10000. Here's an example for a list of size 5, with the timing output suppressed:

   Enter list size: 5
   seed = 461556
   printing array
   [0] = 5390
   [1] = 27070
   [2] = 12590
   [3] = 28419
   [4] = 27104
   
   after insertion sort: 
   [0] = 5390
   [1] = 12590
   [2] = 27070
   [3] = 27104
   [4] = 28419
   
   Enter number to find: 27104
   Linear search: 27104 is at position 3 (time: xxx us)
   Binary search: 27104 is at position 3 (time: xxx us)
   		

   Report on the observed running times.

1. Cover page containing: Course Id--Section No.
   Name:
   SS No:
   Assignment No.
   
2. Assignment description
3. Solution description (e.g., program design, description of algorithm, etc., however appropriate).
4. Lessons learned, identified interesting features of your program
5. Appendix A: Source code listing
6. Appendix B: Sample input (if any)
7. Appendix C: Sample output

The general presentation of your document counts! (This includes qualities such as neatness, formatting, and legibility.)