/*
     CSC 16 lab 4.  Binary Search and Recursion
     Due Thursday 10/6/05

PART I:

You are to adopt the binary search procedures I wrote in class to
work with the "date" objects we implemented previously.  I've posted
my version of this class, and implemented a function to test if two
dates are the same.

Specifically, you need to implement:

  A function that tests if an array of dates is sorted:

      public static boolean sorted(date[] A)

  2 versions of binary search, one with, and one without recursion

  A version of search that does not assume that the array of dates is sorted

  A main that generates a large array of sorted dates depending on a
  command-line parameter.  Call the sort functions on the arrays of
  sizes

  Conduct timing experiments on arrays of sizes 10000, 20000, 30000,
  40000, 50000 (increase/decrease sizes to get meaningful timings)

  As in the experiment I did, to test the algorithms to the fullest, you
  should search for a date that does NOT exist in the array.  This is called
  finding the "worst-case" performance of an algorithm.  

  Graph the results comparing binary search and non-binary search

--------------------------------------------------------------------

PART II:

  According to the great computer scientist Donald E. Knuth, the first true
  "algorithm" was invented by Euclid in ancient Greece to compute the
  greatest common divisor of two numbers.

  We can write the algorithm using a while loop as follows:

  public static int gcd(int a, int b) // computes GCD of a and b
  {
     int temp; // for swaping values
     while (b!=0)
     {
        temp = b;   // record original value of b before it's changed.
        b = a % b;
	a = temp;  // a becomes the original value of b
     }
     return a;
  }

In other words, after each step, a becomes b and b becomes a%b, until
b becomes 0.

For example, to find the gcd of 6 and 15, we go through the following 
values of a and b:
a       b
6       15,   6 % 15 == 6, so
15      6     15 % 6 == 3, so
6       3     6 % 3 == 0, so
3       0     b==0, so stop
answer = 3

You task is to figure out how to write this function RECURSIVELY.
Please implement and test your solution.

*/