Linear search

 

Introduction

Search a list sequentially for a number is also a challenging problem.

Consider a list of numbers in a list on which you need to check whether the number is present or not.

The best way to do this is, compare the number with each number in the list. If its found, return the index, otherwise, return not found.

Here, the loop invariant which holds true always is that there is some index in the list which should be set as output. The initial assumption is the index -1 and while executing also its maintained until when proper index is found. On termination, when the proper index is not found, –1 is returned.

Code

   1:  int search(int *arr, int num, int count)

   2:  {

   3:      for (int i=0; i<count; i++)

   4:      {

   5:          if(arr[i] == num)

   6:              return i;

   7:      }

   8:      return -1;

   9:  }

  10:   

  11:  void main()

  12:  {

  13:      int test_arr[] = {5,3,2,6,8,9};

  14:      int idx = search(test_arr, 6 , 6);

  15:  }

 

This algorithm can be optimized of the list is in sorted order using a method named binary search. Before studying about that, we should understand about an algorithm design approach named Divide and Conquer approach. The approach we used now is sequential approach.

Even Insertion sort explained yesterday is based on sequential approach.

We will see about this tomorrow.