Published: December 5, 2024
Reading Time: 6 minutes
Linear search in C is one of the simplest methods for searching data within a collection. It involves checking each element in a list individually to find the target value. This article explores the fundamentals of linear search and demonstrates how it works through step-by-step implementation in C with practical examples and code.
Linear search algorithm is a method used to find an element in a list or an array. It works the same way we manually search for items in an array.
Analogy: If there is a long shelf with unlabelled boxes storing different hardware items and we need to find something specific, we logically start from one end and search to the other end until it is found.
Similarly, linear search works by sequentially checking each element, starting from the first and going until the desired value is found or the end of the list is reached.
Key Characteristics:
The linear search algorithm follows a straightforward approach to locate a target element in an array:
Step 1: Start from the first element
Begin at index 0 of the array and compare the target value (key) with the element at this index.
Step 2: Check for a match
If the key matches the current element, return its position immediately.
Step 3: Move to the next element
If there's no match, proceed to the next index and compare the key with the new element.
Step 4: Repeat the process
Continue checking each element in sequence until a match is found. Return to the position where the key is located.
Step 5: Handle unsuccessful searches
If the key is not found after checking all elements, display a message stating that the element is not in the array and exit the program.
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
Let's understand how linear search works with a visual example.
Consider an unsorted array where we need to find the element K = 11:
Initial Array:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Value | 70 | 40 | 30 | 11 | 57 | 41 | 25 | 14 | 52 |
Iteration 1: Compare K with index 0
Iteration 2: Compare K with index 1
Iteration 3: Compare K with index 2
Iteration 4: Compare K with index 3
Result: The algorithm returns index 3, where the element is located.
Here is the implementation to find an element in an array. This program searches for the element 10 and returns the index where it is found (index 3 in this case).
#include <stdio.h>
int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, N, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Best Case: O(1)
The key is found at the first index and requires only one comparison.
Worst Case: O(N)
The key is located at the last index, or it is not present at all. In this scenario, the algorithm must traverse the entire list, where N is the size of the list.
Average Case: O(N)
On average, the algorithm will search half the elements in the list before finding the key or concluding it's absent.
Space Complexity: O(1)
Linear search uses a constant amount of auxiliary space since it only requires a single variable to iterate through the list.
Linear search can also be implemented using recursion. Here is the recursive implementation:
#include <stdio.h>
// Define a function to perform the linear search
int linearSearch(int arr[], int size, int key)
{
// If the size of the array is zero, return -1
if (size == 0) {
return -1;
}
// Check if the element at the current index
// is equal to the key
if (arr[size - 1] == key) {
// If equal, return the index
return size - 1;
}
// If not equal, call the function again
// with the size reduced by 1
return linearSearch(arr, size - 1, key);
}
// Driver code
int main()
{
int arr[] = { 5, 15, 6, 9, 4 };
int key = 4;
int index
= linearSearch(arr, sizeof(arr) / sizeof(int), key);
if (index == -1) {
printf("Key not found in the array.\n");
}
else {
printf("The element %d is found at %d index of the "
"given array \n",
key, index);
}
return 0;
}
Linear search is easy to implement and understand, making it a practical choice for beginners to learn with simpler use cases.
Linear search is often the basic method for searching elements in unsorted arrays or lists since it doesn't require prior sorting.
In linked list structures, linear search is widely used to locate elements. Each node is traversed sequentially until the target value is found.
For smaller datasets, linear search is preferred over algorithms like binary search due to its straightforward logic and minimal overhead.
This article provides a comprehensive introduction to linear search in C. With the examples and code implementations provided, you should be able to understand the concepts and apply them to other searching problems.
To advance your skills further, it's important to solve more advanced search examples. The best place to learn would be a tailored program that prepares you for real-world jobs. Enroll in CCBP 4.0 Academy to start on your professional journey.
Linear search in C is a simple algorithm for searching. It checks each element in a list sequentially to find the target value.
The algorithm starts from the first element and compares each one with the target. Once a match is found it returns the value or the list ends without the target being in the list.
Linear search is preferred for unsorted data, small datasets, and when simplicity in implementation is required.
Yes, linear search in data structure using C is often used in arrays, linked lists, or any collection that allows sequential traversal.
Linear search is used in tasks like looking up names in unsorted directories or searching for specific values in small datasets.
About NxtWave
NxtWave offers comprehensive programming courses through CCBP 4.0 Academy to help students and professionals build real-world development skills.
Contact Information:
Course Offerings: