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) ); 

  

  

       // Table headings 

       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 

             printf("NOT FOUND \t"); 

  

       // 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 

   //to value at that address 

  

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

    { 

      *comparisons = *comparisons + 1;  

                  //about to do a comparison 

  

      if (array[counter] == key) 

         return FOUND;     // Key found! 

    } 

  

   return NOT_FOUND;           // Key not found 

 }

Again i would apreciate all help.
Thanks
Peace!!

>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. ;)

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!

This article has been dead for over six months. Start a new discussion instead.