Searching is one of the most common operations in programming. In C, a linear search is the simplest method to find an element in an array. It works by checking each element of the array one by one until the desired value is found or the array ends. This technique is ideal for beginners because it helps understand arrays, loops, and conditional statements. In this tutorial, we will write a C program to perform a linear search.
Linear search is easy to implement and works for both small and unsorted arrays. While it may not be the most efficient search method for large datasets, it provides a clear understanding of how arrays are traversed in memory. By practicing linear search, beginners learn how to combine loops and conditionals effectively, which is a foundation for learning more advanced algorithms like binary search.
Understanding the Problem
In linear search, we start from the first element and compare each element with the target key. The search stops when the key is found or when all elements have been checked. While iterative linear search is straightforward, recursive linear search offers an alternative approach by reducing the problem size with each recursive call.
Program 1: Iterative Linear Search
This program demonstrates searching an element in an array using a loop. The function returns the index of the element if found, or -1 if not found.
#include <stdio.h>
// Iterative linear search function
int linearSearchIterative(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key)
return i; // Element found at index i
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = linearSearchIterative(arr, size, key);
if (result != -1)
printf("%d found at index %d\n", key, result);
else
printf("%d not found in the array\n", key);
return 0;
}In the iterative approach, we loop through each element sequentially. If the key matches an element, the index is returned immediately; otherwise, the search continues until the array ends. This method is efficient for small arrays but can be slower for large datasets.
Program 2: Recursive Linear Search
This program demonstrates searching an element using recursion. Each recursive call checks one element and reduces the problem size by advancing the starting index.
#include <stdio.h>
// Recursive linear search function
int linearSearchRecursive(int arr[], int size, int key, int index) {
if (index >= size)
return -1; // Element not found
if (arr[index] == key)
return index; // Element found
return linearSearchRecursive(arr, size, key, index + 1); // Check next element
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr)/sizeof(arr[0]);
int key = 40;
int result = linearSearchRecursive(arr, size, key, 0);
if (result != -1)
printf("%d found at index %d\n", key, result);
else
printf("%d not found in the array\n", key);
return 0;
}The recursive approach divides the problem into smaller subproblems by checking one element at a time and calling itself for the next index. Recursion can make the code cleaner, but it uses additional stack memory for each call.
FAQs
Q1: What is the time complexity of linear search?
The time complexity is O(n) in both best and worst cases for unsorted arrays.
Q2: Can linear search be used on sorted arrays?
Yes, but binary search is more efficient for sorted arrays.
Q3: Which is better: recursive or iterative linear search?
Iterative is generally more efficient because recursion uses extra stack memory. Recursive may be preferred for educational or illustrative purposes.
Q4: Can linear search be used for linked lists?
Yes, linear search works on linked lists by traversing each node sequentially.
Conclusion
Linear search is a simple and reliable searching algorithm for small or unsorted datasets. Understanding both iterative and recursive implementations strengthens your programming fundamentals. While iterative search is memory-efficient, recursion provides a clean, elegant alternative for learning purposes.
References & Additional Resources
A curated list of trusted books, tutorials, and guides to deepen understanding of C programming and search algorithms.
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A traditional and respected textbook covering core C concepts and fundamental data structures, including search algorithms like linear search.
- Linear Search – GeeksforGeeks – Simple and clear explanation of linear (sequential) search, showing how each array element is checked until the target is found or the list ends.
- Linear Search – Programiz – Straightforward guide describing how linear search works step by step, with examples in C and other languages.
- Exploring Time and Space Complexities of Linear Search – Programiz PRO – Analytical breakdown of linear search’s time complexity: best-case O(1), average and worst-case O(n).
- Linear Search – Wikipedia – Encyclopedic overview of linear search, including algorithm details, complexity, optimizations like sentinel usage, and real-world practicality on short lists.
- Searching Algorithms – GeeksforGeeks – Wide-ranging tutorial on search algorithms, including linear and binary search comparisons and when to use each.
