What is Linear Search? Explain Linear Search with C source code. How efficient is this type of search?

Searching
Computers are often used for large data storage of records like databases. Searching a record from billions of records and fetching it from file system is a time critical task. Time taken to find a random record decides the performance of the search algorithms. Several search algorithms have been invented to reduce this search time.

Linear Search
Linear search is a basic form of search. It basically iterates through all the records in the table and stopped when it found the desired record.
Example: Say we have n records record[];

record_t * linear search(int id)
{

  for(i = 0; i < n; i++)
  {
    if(record[i].id == id)
    {
      return 
    }
  }
}

Advantage:

1. It is very easy to implement. Thus code complexity is low.
2. This method is very useful and efficient when dealing with small number of records.

Disadvantage:

1. When the number of the records grows it becomes very slow as the O(n).
2. This method cannot be used in large records.

Code:

int linear_search(int low_indx, int high_indx, 
                  int record[], int record_val)
{
  int index;
  for(index = low_indx; index < high_indx; index++)
  {
    printf("Iteration %d \n",index);
    if(record[index] == record_val)
    {
      return index;
    }
  }
  return -1;

}

int main(int argc, char *argv[])
{
  int records[20] =
  {
    0, 3, 6, 7, 8, 9, 10, 13, 14, 16,
    19, 20, 25, 27, 29, 31, 32, 38, 40, 41
  };
  int record_index, record;
  printf("Search element:");
  scanf("%d", &record);
  printf("\nLinear Search\n");
  record_index = linear_search(0, 20, records, record);

  if(record_index == -1)
  {
    printf("Record not found!");
  }
  else
  {
      printf("Record index %d", record_index);
  }
  return 0;
}

About our authors: Team EQA

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›