// CS 305 - Computer Algorithms I
// Fall 2003
//
// An array-recursive implementation of linear search.

#include <cassert>
#include <cstdlib>
#include <unistd.h>


static int 
find1(int arr[], unsigned i, unsigned n, int x) {

  // Return the index of the element in arr[i..n-1] equal to x or -1 if there's
  // no such element.

  // The empty array.

     if (i >= n)
       return -1;

  // The element.

     if (arr[i] == x)
       return i;

  // The rest of the array.

     return find1(arr, i + 1, n, x);
  }


static int 
find2(int arr[], unsigned n, int x) {

  // Return the index of the element in arr[0..n-1] equal to x or -1 if there's
  // no such element.

  for (unsigned i = 0; i < n; i++)
    if (arr[i] == x)
      return i;

  return -1;
  }


static void
test() {

  // Check find1() against find2().

  const unsigned 
    max = 10000,
    n = (random() % max) + 1,
    x = random() % n;

  const int out = random();

  int * const arr = new int[n];

  for (unsigned i = 0; i < n; i++)
    do arr[i] = random();
    while (arr[i] == out);

  assert(find1(arr, 0, n, arr[x]) == find2(arr, n, arr[x]));
  assert(arr[find1(arr, 0, n, arr[x])] == arr[x]);
  assert(find1(arr, 0, n, out) == -1);

  delete [] arr;
  }


int
main() {
  srandom(getpid());
  for (unsigned i = 0; i < 100; i++)
    test();
  }


// $Log: find.cc,v $
// Revision 1.1  2003/09/19 19:16:34  rclayton
// Initial revision
//