//---------------------------------------------------------------------
//  Sınislausn á dæmi 2 á Vikublaği 5 í Tölvunarfræği 2, vor 2005
//
//  Hjálmtır Hafsteinsson, febrúar 2005
//---------------------------------------------------------------------
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

// Runuleitarfalliğ út Algorithms-bókinni
int search(int a[], int v, int l, int r)
{ 
	for (int i = l; i <= r; i++)
		if (v == a[i]) return i;
	return -1;
}


// Şağ şurfti ağ hækka M og N uppí 10000 til ağ fá mælanlegan tíma.  Gildin
//  sem beğiğ er um í kennslubókinni eru alltof lítil.  Şegar bæği M og N eru
//  10000 şá tók leitunin 0.78 sek. og şağ fundust 2652 tölur (af şessum 10000)
int main()
{
	int N, M;
	int i;
	clock_t upph, lok;

	// Upphafsstilla slembitölugjafa
	srand( (unsigned)time( NULL ) );


	for( M=10; M<=10000; M*=10 ) {

		int *A = new int[M];
		for( i=0; i<M; i++ )
			A[i] = rand();

		for( N=10; N<=10000; N*=10 ) {

			// Leita ağ N slembitölum í fylkinu
			upph = clock();
			int fundnar = 0;
			for( i=0; i<N; i++ )
				if( search( A, rand(), 0, M-1 ) != -1 )
					fundnar++;
			lok = clock();

			cout << "Fyrir M=" << M << " og N=" << N << " fundust " << fundnar <<
				  " tolur a " << double( lok-upph ) / CLOCKS_PER_SEC << " sek." << endl;				

		}

		delete[] A;

	}

	return 0;
}