Data Structures(Linear search in data structures)

Searching:

👉  Searching is the process of finding some particular element in the list. 

👉  If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

👉  There are two popular search methods that are widely used in order to search some item into the list. 

            🔯   Linear Search

            🔯   Binary Search

Linear Search

👉  Linear search is the simplest search algorithm and often called sequential search. 

👉  In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. 

👉  If the match found then location of the item is returned otherwise the algorithm return NULL.

👉  Linear search is mostly used to search an unordered list in which the items are not sorted.

Technique:

The steps used in the implementation of Linear Search are listed as follows -

• First, we have to traverse the array elements using a for loop.
• In each iteration of for loop, compare the search element with the current array element, and -
  • If the element matches, then return the index of the corresponding array element.
  • If the element does not match, then move to the next element.
• If there is no match or the search element is not present in the given array, return -1.

Algorithm

LINEAR_SEARCH(A, N, VAL)

Step 1: [INITIALIZE] SET POS = -1

Step 2: [INITIALIZE] SET I = 1

Step 3: Repeat Step 4 while I<=N

Step 4: IF A[I] = VAL

SET POS = I

PRINT POS

Go to Step 6

[END OF IF]

SET I = I + 1

[END OF LOOP]

Step 5: IF POS = -1

PRINT " VALUE IS NOT PRESENTIN THE ARRAY "

[END OF IF]

Step 6: EXIT

Complexity of algorithm

Complexity         Best Case         Average Case         Worst Case

Time                     O(1)                 O(n)                         O(n)

Space                                                                             O(1)

Working of Linear search:

Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the next element. And follow the same process until the respective element is found.

Now, the element to be searched is found. So algorithm will return the index of the element match

Implementation of Linear Search:

#include <stdio.h>

#include <conio.h>

void main()
{
  int a[10], search, i, n;

  printf("Enter number of elements in array\n");
  scanf("%d", &n);

  for (i = 0; i < n; i++)

    scanf("%d", &a[i]);

  printf("Enter a number to search\n");
  scanf("%d", &search);

  for (i = 0; i < n; i++)
  {
    if (a[i] == search)    /* If required element is found */
    {
      printf("%d is present at location %d.\n", search, i+1);
      break;
    }
  }
  if (i == n)
    printf("%d isn't present in the array.\n", search);

 
}

OUTPUT: