//######################################################################
// Determine the average case performance of linear search. Generate
// SIZE+1 random numbers in array a[0..SIZE]. Randomly pick one of the
// SIZE+1 numbers and use linear-search to look for the number in the
// a[0..size-1]. This is repeated RUNS times, and the average times of
// comparison performed by linear-search is calculated.
// The expected value is:
// 1/(SIZE+1) (1+2+3+...+SIZE + SIZE)
//######################################################################

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10
#define RUNS 10000
#define RANGE 10000


int linear_search(int val, int arr[], int size)
{
  int i;

  for(i = 0; i < size; ++i)
    if(arr[i] == val) return i;

  return -1;
}

int main()
{
    int a[SIZE+1], i, j, waldo, total, result;

    total = 0;

    for(i=0; i<RUNS; i++) {
        // create an array of random numbers
        for(j=0; j<SIZE+1; j++) {
            // number is between 0 and RANGE-1
            a[j] = (int) (rand()/(RAND_MAX+1.0) * RANGE);
        }

        // waldo is the number randomly picked from a[0..SIZE].
        // if a[SIZE] is picked, it won't be found by linear-search.
        waldo = a[(int) (rand()/(RAND_MAX+1.0) * (SIZE+1))];

        result = linear_search(waldo, a, SIZE);

        //printf("result = %d\n", result);

        if(result == -1) // not found
            total += SIZE; // SIZE comparisons have been performed
        else
            total += result+1; // result+1 comparisons have been performed
    }

    printf("Everage comparisons performed = %f\n", (double)total/RUNS);
}