Linear Search in C

How Does Linear Search Algorithm Work?

In linear search, each and every element of the array is compared with the given specific value one by one. Search continues until the value is found or does not reach the end of the array. A linear search starts from the beginning of the array and then examines every element of the array until a match is found or the end of the array is reached. The element's index is returned as an output if the specified value is found. If the specified value is not found, a special value say ‘-1’ is returned to indicate that the value was not found or it may be some other value indicating that element was not found. Linear search is a straightforward and easy-to-understand algorithm, but more efficient ways exist to search through a large dataset. Linear search is best used when given small datasets or unsorted or unsorted arrays generally.

Approach to Implement Linear Search in C

To implement linear search in C, the following steps are given:

1. Define an array of elements to search.
    
2. Define the specific value to search in a given array.
    
3. Use the Iteration technique, which compares the search value to a specific value.
    
4. If the search value is found, return the index of the element. Otherwise, continue iterating through the array until we reach the end of the array.
    
5. If the end of the array is reached and the search value has not been found, return a special value like -1 to indicate that the value was not found. The return value might vary from problem to problem. It was just to demonstrate what to return in case element wasn't found.

Implementation of Linear Search Program in C

Below is the implementation of linear search in C.

Implementation in C

• C

C

#include<stdio.h>

int main()
{
    int n,search,count=0;
    printf("Enter the number of elements in array: ");
    scanf("%d",&n);
    printf("%d\n",n);

    int array[n];
    printf("Enter the number in array: ");

    for(int i=0;i<n;i++)
    {
        scanf("%d",&array[i]);
    }

    for(int i=0;i<n;i++)
    {
        printf("%d ",array[i]);
    }

    printf("\nEnter the search number: ");
    scanf("%d",&search);
    printf("%d\n",search);

    for(int i=0;i<n;i++)
    {
        if(array[i] == search)
        {
            printf("%d is present in the array at index %d.\n",search,i+1);
            count++;
        }
    }

    if(count==0)
	    printf("%d is not present in the array.\n",search);
    else
	    printf("%d is present %d times in the array.",search,count);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Explanation

In the above code, we have declared an array of elements and a target value named as search. We have also taken a count variable in which we will store the frequency of search value. The algorithm starts by setting the initial index of the array to 0. It then compares the element at the current index with the search value. If the element matches the search value, the algorithm prints the index and increases count variable by 1. If the element does not equal the search value, the algorithm increments the index by 1. This process continues until the search value is found or the end of the array is reached. If the search value is not found in the array then count variable must be 0. So, the algorithm prints that search value is not present in the array.

Also see, Floyd's Triangle in C

Time and Space Complexity of Linear Search in C

Time and space complexity are essential concepts in computer science. It is used to analyze the efficiency of algorithms. In C language, an algorithm's time and space complexity can be analyzed using Big O notation.

1. The time complexity of linear search in C is O(N). N is the size of the array being searched. This is because, in the worst-case scenario, the linear search must check each element in the array individually until it finds the targeted value or reaches the end of the array.
    
2. The space complexity of linear search in C is O(1). It means that it requires a constant amount of memory. This is because linear search does not require additional data structures or memory allocations - it simply uses a single variable to track the current examined index.
    
3. Overall, linear search is a simple algorithm. Its time complexity of O(N) and space complexity of O(1).

Linear Search in C for Multiple Occurrences

Below is the Linear Search in C for Multiple Occurrences.

Implementation in C

• C

C

#include <stdio.h>
int main() {
   int n, search, i;
   
   // Input the number of elements in the array
   printf("Enter the number of elements: ");
   scanf("%d", &n);
   
   int arr[n];
   
   // Input the elements of the array
   printf("Enter the elements:\n");
   for (i = 0; i < n; i++) {
       scanf("%d", &arr[i]);
   }
   
   // Input the element to be searched
   printf("Enter the element to search for: ");
   scanf("%d", &search);
   
   int found = 0; // To keep track of occurrences
   
   // Linear search
   for (i = 0; i < n; i++) {
       if (arr[i] == search) {
           printf("Element found at index %d\n", i);
           found = 1;
       }
   }
   
   if (!found) {
       printf("Element not found in the array.\n");
   }
   
   return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Enter the number of elements: 4
Enter the elements:
1
2
3
4
5
Enter the element to search for: 3
Element found at index 2

Program for Linear Search in C Using a Function

Below is the program for linear search in C using a function named linear search function.

Implementation in C

• C

C

#include<stdio.h>

//function prototype
int linear_search_function(int*, int, int);

//main function
main()
{
   int array[100], target, c, n, pos;
 
   printf("Enter the number of elements in array\n");
   scanf("%d",&n);
 
   printf("Enter %d numbers\n", n);
 
   for ( c = 0 ; c < n ; c++ )
      scanf("%d",&array[c]);
 
   printf("Enter the number to search\n");
   scanf("%d",&target);
 
   pos = linear_search_function(array, n, target);
 
   if ( pos == -1 )
      printf("%d is not present in array.\n", target);
   else
      printf("%d is present at position %d.\n", target, pos+1);
 
   return 0;
} 

//function definition
int linear_search_function(int *pointer, int n, int target)
{
 
   for ( int i = 0 ; i < n ; i++ )
   {
      if ( *(pointer+i) == target)
         return i;
   }
 
   return -1;
}

You can also try this code with Online C Compiler

Run Code

Output

Enter the number of elements in array
10
Enter 10 numbers
1 3 5 6 7 10 2 4 8 9
Enter the number to search
7
7 is present at position 5.

Explanation

In the above code, we created a function named as linear search function with three parameters. Here the main method is calling our defined function to find the position of the target value. The linear Search function() searches for the desired element within the array. The function will save the value in the variable "pos" of the main function and return the index of the target element that was located, or else return -1. Here the Time Complexity is O(n) because we are traversing the array of elements using a loop in a linear search function. The space complexity is O(1) as we are not using any extra space.

Linear Search Function Using Pointers

Using pointers to perform a linear search can make the function more versatile and adaptable to different data types. Let's see how you can implement a linear search using pointers in C:

• C

C

#include <stdio.h>

int* linearSearch(int *arr, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (*(arr + i) == key) {
            return (arr + i);
        }
    }
    return NULL;
}

int main() {
    int arr[] = {4, 2, 8, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 6;
    int *found = linearSearch(arr, n, key);

    if (found != NULL) {
        printf("Element found at index %ld\n", found - arr);
    } else {
        printf("Element not found\n");
    }
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Advantages of Linear Search in C

The advantages of linear search in C include the following:

• Simplicity: Easy to understand and implement, making it beginner-friendly.
   
• Versatility: Applicable to arrays of any size and content.
   
• Efficiency for Small Data: Performs well with small data sets, as it doesn't involve complex pre-processing.

Disadvantages of Linear Search in C

The disadvantages of linear search in C include the following:

• Inefficiency with Large Data Sets: Linear search becomes slower as the data set size increases, as it checks every element sequentially (time complexity O(N)).
   
• Inefficiency with Sorted Data: It's not efficient for sorted arrays, as it doesn't take advantage of the data's order.
   
• Lack of Optimization: Linear search lacks optimization techniques found in more efficient algorithms, making it less suitable for large or time-sensitive applications.

Frequently Asked Questions

What is the time function in linear search in C?

In C, the `time` function is not specifically part of a linear search. However, you can use `time(NULL)` from `<time.h>` to measure the execution time of a linear search by capturing timestamps before and after the search operation.

What is linear search with example?

A linear search starts from the beginning of the array and then examines every element of the array until a match is found or the end of the array is reached. The element's index is returned as an output if the specified value is found. 

What is linear search program in C using array function?

Linear search program in C using the array function is simple and flexible to implement. The main method calls the defined array function to find the position of the target value. The array function  searches for the desired element within the array.

What is linear pattern search in C?

Linear Pattern Search in C is a simple string-matching algorithm that checks for a pattern in a text sequentially. It compares characters one by one, making it easy to implement.

Conclusion

So far, we have discussed a lot about Linear Search in C. We have came to the end of the blog. We hope this blog adds knowledge to you. In conclusion, linear search is a simple and flexible search algorithm. Mainly used for small data sets or unordered data. Its time complexity is O(N), and the space complexity of O(1). This means that it does not require any extra memory beyond the array being searched. The linear search may not be the most efficient algorithm for large or sorted data sets. For large datasets, other search algorithms, like binary search, are more appropriate. Overall, linear search is a basic algorithm that can be useful in simple search applications.

Also check out our other articles: 

• Multilevel Inheritance in Java
• Time Complexity of Sorting Algorithms
• Addressing Modes in Computer Architecture