You are here

Linear search in C

Linear search in C programming: The following code implements linear search (Searching algorithm) which is used to find whether a given number is present in an array and if it is present then at what location it occurs. It is also known as sequential search. It is straightforward and works as follows: We keep on comparing each element with the element to search until it is found or the list ends. Linear search in C language for multiple occurrences and using function.

Linear search C program

  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5.   int array[100], search, c, n;
  6.  
  7.   printf("Enter number of elements in array\n");
  8.   scanf("%d", &n);
  9.  
  10.   printf("Enter %d integer(s)\n", n);
  11.  
  12.   for (c = 0; c < n; c++)
  13.     scanf("%d", &array[c]);
  14.  
  15.   printf("Enter a number to search\n");
  16.   scanf("%d", &search);
  17.  
  18.   for (c = 0; c < n; c++)
  19.   {
  20.     if (array[c] == search)    /* If required element is found */
  21.     {
  22.       printf("%d is present at location %d.\n", search, c+1);
  23.       break;
  24.     }
  25.   }
  26.   if (c == n)
  27.     printf("%d isn't present in the array.\n", search);
  28.  
  29.   return 0;
  30. }

Output of program:
Linear search C program

Download Linear search program.

C program for binary search

Linear search for multiple occurrences

In the code below we will print all the locations at which required element is found and also the number of times it occur in the list.

  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5.    int array[100], search, c, n, count = 0;
  6.    
  7.    printf("Enter number of elements in array\n");
  8.    scanf("%d", &n);
  9.    
  10.    printf("Enter %d numbers\n", n);
  11.    
  12.    for (c = 0; c < n; c++)
  13.       scanf("%d", &array[c]);
  14.      
  15.    printf("Enter a number to search\n");
  16.    scanf("%d", &search);
  17.    
  18.    for (c = 0; c < n; c++) {
  19.       if (array[c] == search) {
  20.          printf("%d is present at location %d.\n", search, c+1);
  21.          count++;
  22.       }
  23.    }
  24.    if (count == 0)
  25.       printf("%d isn't present in the array.\n", search);
  26.    else
  27.       printf("%d is present %d times in the array.\n", search, count);
  28.      
  29.    return 0;
  30. }

Download Linear search multiple occurrence program.

Output of code:
Linear Search program output for multiple occurrence

C program for linear search using function

  1. #include <stdio.h>
  2.  
  3. long linear_search(long [], long, long);
  4.  
  5. int main()
  6. {
  7.    long array[100], search, c, n, position;
  8.  
  9.    printf("Input number of elements in array\n");
  10.    scanf("%ld", &n);
  11.  
  12.    printf("Input %d numbers\n", n);
  13.  
  14.    for (c = 0; c < n; c++)
  15.       scanf("%ld", &array[c]);
  16.  
  17.    printf("Input a number to search\n");
  18.    scanf("%ld", &search);
  19.  
  20.    position = linear_search(array, n, search);
  21.  
  22.    if (position == -1)
  23.       printf("%d isn't present in the array.\n", search);
  24.    else
  25.       printf("%d is present at location %d.\n", search, position+1);
  26.  
  27.    return 0;
  28. }
  29.  
  30. long linear_search(long a[], long n, long find) {
  31.    long c;
  32.  
  33.    for (c = 0 ;c < n ; c++ ) {
  34.       if (a[c] == find)
  35.          return c;
  36.    }
  37.  
  38.    return -1;
  39. }

Linear search function using pointers

  1. long linear_search(long *pointer, long n, long find)
  2. {
  3.    long c;
  4.  
  5.    for (c = 0; c < n; c++) {
  6.       if (*(pointer+c) == find)
  7.          return c;
  8.    }
  9.  
  10.    return -1;
  11. }

Time required to search an element using linear search algorithm depends on size of the list. In the best case it is present at the beginning of the list and in the worst case element is present at the end. The time complexity of linear search is O(n).