Updated April 7, 2023
Introduction to Linear Search in C
The linear search in C is used to search for an element in an array in sequential order. In C, use a linear search to see whether a number is in an array. If it is present, then at what location it is present. Linear searches also known as sequential searches. In this form of searching, we simply go through the entire list from left to right and match each element to the item whose location needs to be identified. If a match is found, the algorithm returns the item’s location; otherwise, NULL is returned. The worst-case running time complexity of the linear search is O(n), the best-case running time complexity is O(1)and the average-case running time complexity is O(n).
A straightforward method for implementing a linear search is:
- Start from the left to right elements of an array and compare the search value to each element of an array, one by one.
- If the search value is equal to an element, then return the index.
- Else return -1 if the search value does not equal any of the elements.
The algorithm of the shell sort –
Linear_search(arr, n, search_value)- Step 1: Set pos to 1.
- Step 2: if pos> n then go to step 7.
- Step 3: if arr[pos] = search_value then go to step 6.
- Step 4: Set pos to pos + 1.
- Step 5: Go to Step 2.
- Step 6: Print the search element search_value present at index pos and then go to step 8.
- Step 7: Print the search element not present in an array.
- Step 8: Exit.
Return value – The return value of this algorithm is the index value of the searching element.
Working of the Linear Search Algorithmin C
The working of the linear search algorithm in C
- Let the specified array and search element are –
Given array: [8, 7, 2, 6, 4, 5, 4, 0] and search element: 4.
- The search element 4 is compared with the first element 8. Both elements are not equal. So search moves to the next element.
- Next, search element 4 is compared with the second element 7. Both elements are not equal. So search moves to the next element.
- The search element 4 is compared with the third element 2. Both elements are not equal. So search moves to the next element.
- The search element 4 is compared with the fourth element 6. Both elements are not equal. So search moves to the next element.
- The search element 4 is compared with the fifth element 4. Both elements are equal. So stop the searching farther and displays the index of an element that is 4(because the index starts from 0).
Examples for Linear Search Algorithm in C
Example for linear search in C to search an element in the array of numbers.
Example #1
Code:
#include
int Linear_search(int arr[], int n, int val)
{
int idx;
for (idx = 0; idx< n; idx++)
{
if (arr[idx] == val)
{
return idx;
}
}
return -1;
}
int main(void)
{
int arr[] = { 12, 13, 14, 20, 41, 45 };
int search_value = 20;
int n = sizeof(arr) / sizeof(arr[1]);
int index = Linear_search(arr, n, search_value);
if(index == -1)
{
printf("The search element is not in array");
}
else
{
printf("The search element is found at index %d", index);
}
return 0;
}Output:
As in the above program, the Linear_search() function is created to search the number in a given array. Inside the function, the for loop used to iterates all the elements of an array, and inside the for loop compares whether the search element is equal to the current iterating element or not. When both are equal, then return the index and stop the for a loop. When the for loop completes and does not match with the search element then return -1. Then in the main function after calling the return result of the Linear_search() function checks and print the appropriate statement, as we can see in the above output.
Example #2
Example for linear search in C to search an element in the array of numbers for multiple occurrences-
Code:
#include
int Linear_search(int arr[], int n, int val)
{
int idx, count = 0;
for (idx = 0; idx< n; idx++)
{
if (arr[idx] == val)
{
printf("%d is found at index %d.\n", val, idx);
count++;
}
}
return count;
}
int main(void)
{
int arr[] = { 12, 13, 14, 20, 41, 45, 20 };
int search_value = 20;
int n = sizeof(arr) / sizeof(arr[1]);
int res = Linear_search(arr, n, search_value);
if(res == 0)
{
printf("The search element is not in the array.");
}
else
{
printf("The search element is found %d times in the array.", res);
}
return 0;
}Output:
As in the above program, the Linear_search() function is created to search the number in a given array and its count. Inside the function, the for loop is used to iterates all the elements of an array, and inside the for loop compares whether the search element is equal to the current iterating element or not. When both are equal, then print the index value and increment the count value and continue the for a loop. When the for loop completes, then return count value. Then,in the main function after calling the return count of the Linear_search() function checks and print the appropriate statement, as we can see in the above output.
Recommended Articles
This is a guide to Linear Search in C. Here we also discuss the introduction and working of the linear search algorithm in C along with an example and its code implementation. You may also have a look at the following articles to learn more –
