Hello ppl.
Ok have to investigate and write a report on the efficiency of the following Linear Search algorithm.
But im having problems starting off.... can anyone here help me kick start this 3 page report... would apreciate any information & help you guys here can give.

``````//   This program randomly generates a series of test data of

// differing sizes

//   (5 - 100 positive integers) reading them into array a.

//   It then randomly generates a search key

//   and searches the elements of the array using linear search.

//   It returns a table giving the amount of data the test was

//   run on and the number of comparisons made.

#include <stdlib.h>

// Make standard library available eg for random number

// generation functions

#include <stdio.h>     // Make input/output  library available

#include <time.h>

// define a new type called SearchResult

//(like int is already a type)

//There are two values (like 1, 2,3 etc are values for ints)

// of type searchResult: FOUND and NOT_FOUND

enum SearchResult {FOUND, NOT_FOUND};

// List the functions in this program

SearchResult linearSearch

(int array[], int key, int sizeOfData, int *comparisons);

void fill_array(int array[], int sizeOfData);

const int RANGE = 200; // random data used in range 0-199

int main()

{

const int arraySize = 100;

int a[arraySize];

FILE *resultsFile;

resultsFile = fopen("lsrch.dat", "w");

// open the file lsrrch.dat for writing ("w")

if (resultsFile != NULL)      // file successfully opened

{

// seed the random number generator so it gives different

// random numbers each time

srand ( time (0) );

printf ("Found\t Data Size\t Comparisons Needed\n"  );

//\t puts in a tab character, \n a new line

fprintf(resultsFile,"Data Size\t Comparisons Needed\n");

// Generate table for data of different sizes

// giving number of comparisons each time

for (int datasize = 1; datasize <= arraySize; datasize = datasize+1)

{

int count = 0;  // number of comparisons this time

SearchResult result; // result of this search

int searchKey = rand() % RANGE;

fill_array(a, datasize);

result = linearSearch(a, searchKey, datasize, &count);

// Note address of count passed - so by reference

if (result == FOUND)

printf("KEY FOUND \t");

else

// print results in a table

printf("%d  \t\t\t  %d\n", datasize, count);

fprintf(resultsFile, "%d  \t\t\t  %d\n", datasize,count);

}

}

else

fprintf(resultsFile, "File not opened\n");

fclose(resultsFile); return 0;

}

// generate random data in range 0-20 and fill the

// array with it up to the given size

void fill_array(int array[], int sizeOfData)

{

for (int counter = 0; counter < sizeOfData; counter++)

{

array[counter] = rand () % RANGE;

}

}

// A linear search function that returns the number of

// comparisons

// call by value as well as a direct indication of found or not.

SearchResult linearSearch

(int array[], int key, int sizeOfData, int * comparisons)

{

*comparisons = 0;  // count comparisons made

//Note comparisons passed by reference so use * to refer

for (int counter = 0; counter < sizeOfData; counter++)

{

*comparisons = *comparisons + 1;

if (array[counter] == key)

return FOUND;     // Key found!

}

}``````

Again i would apreciate all help.
Thanks
Peace!!

All 4 Replies

>can anyone here help me kick start this 3 page report
You have to write a 3 page report about how linear search has linear time? :?: I can summarize in two sentences. Linear search performs O(N) comparions in the worst case, and O(N/2) comparisons in the average case. The worst case is an unsuccessful search that goes through all items and the average case takes advantage of an assumed random distribution where a match will be made, on average, half way through the list.

Good luck adding the filler to that. ;)

yeh i know . thats all i had too. aparently i need to investigate it check the attachment i was given an example , but i still dont seem to kick start it..
What u said is all i got but written it in about 15 lines..

Linear search performs O(N) comparions in the worst case, and O(N/2) comparisons in the average case.

In a related note, linear search also performs O(N/10000) comparisons in the average case!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.