Linear Search Program in C

Last Updated on August 18, 2023 by Mayank Dham

Linear search, a fundamental algorithm in computer science, is the simplest method for finding an element within a collection. While more sophisticated algorithms like binary search exist, linear search provides a solid foundation for understanding basic search operations. In this article, we delve into the world of linear search and explore how to implement a linear search program in the C programming language. Through this journey, we’ll unravel the underlying logic, analyze its efficiency, and gain insights into the broader realm of algorithmic problem-solving.

What is Linear Search Program in C?

A sequential search algorithm is another name for linear search. It is the most straightforward search algorithm. In a linear search, we just go through the list in its whole and match each element with the item whose position has to be found. The algorithm returns the item’s location if a match is made; otherwise, it returns NULL.

It is frequently used to search for a certain element in an unordered list or a list where the entries are not sorted. The linear search’s worst-case time complexity is O(n).

Steps of Linear Search

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.
Now, let’s see the algorithm of linear search.

Linear Search Algorithm:

let’s say the array is X and the value is i;

• Set j to 1
• If j > n, jump to step 7
• If X[j] == i, jump to step 6
• Then, increment j by 1 i.e. j = j+1
• Go back to step 2
• Display the element i which is found at particular index i, then jump to step 8
• Display element not found in the set of input elements.
• Exit/End
  

  How Linear Search Algorithm Work?

  To find an element in the list below with the value k = 1, follow these steps.
  
  Array to be searched for

1. Compare each element x with k starting with the first element.
   

2. Return the index if x == k.
   

3. Else, return not found.

C Program Code for Linear Search

#include <stdio.h> 
int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 
int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
    else
    printf("Item is present at index %d", res);    
	return 0; 
}

Linear Search Complexities:

Time complexity: O(N) will be the time complexity for performing linear search.

Space complexity: O(1) will be the space complexity for performing linear search.

Conclusion
In the realm of search algorithms, the linear search stands as a straightforward yet crucial technique. This article has walked you through the creation of a linear search program in C, emphasizing its simplicity and practicality for searching elements within arrays. While it may not be the most efficient method for larger datasets, linear search shines when dealing with small collections or unsorted data. By grasping the principles of linear search, you’ve unlocked the door to more complex search algorithms and gained valuable insights into problem-solving using C.

FAQ for Linear Search Program in C

Here are few FAQs related to C program for linear search.

Q1: What skills can I gain from implementing a linear search program in C?
Creating a linear search program in C enhances your skills in array manipulation, conditional statements, loops, and algorithmic thinking. It provides a foundational understanding of search algorithms and how to tackle basic search problems.

Q2: How does a linear search work?
Starting from the first element, the linear search compares each element with the target value until a match is found or the end of the list is reached. If the target is found, the index of the element is returned.

Q3: When should I use a linear search?
Linear search is suitable for small datasets or situations where the data is unsorted. It’s not as efficient as binary search for large datasets, but it’s a good choice for simple and quick searches.

Q4: What is the time complexity of linear search?
In the worst case scenario, where the element is not found, the linear search takes O(n) time, where n is the number of elements in the list. In the best case scenario, where the element is found at the beginning, it takes O(1) time.

Q5: Can linear search be used with different data types?
Yes, linear search can be used with different data types. However, you’ll need to modify the comparison logic based on the data type being used.

Q6: How does linear search compare to binary search?
Binary search is more efficient than linear search for larger datasets, as it divides the search space in half with each comparison. However, binary search requires the data to be sorted, whereas linear search works with unsorted data.

Q7: Can linear search be used for complex data structures?
Yes, linear search can be adapted to search for elements in complex data structures like linked lists, but its efficiency might vary depending on the structure’s characteristics.

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C