Linear Search Algorithm In C, Data Structure And Tutorials

Q: What is a linear search algorithm in C?

Ans: A Linear Search algorithm is used to find an element in an array sequentially.

Q: What is the worst-case time complexity of the linear search algorithm?

Ans: The worst-case time complexity of a linear search algorithm is O(N).

Q: Why is the linear search algorithm not preferred in sorted arrays?

Ans: A linear search algorithm iterates over all the element in the array to find the element. However, an optimal approach to using the Binary search can find the element in a time complexity of O(logN).

There are various methods of searching for an element in a list, such as binary search, linear search, etc. The search is unsuccessful if we cannot find an element in the list.

However, we will return the element’s position if it is present in the list. In this article, we will learn about the linear search algorithm used to find the elements in a group of elements, such as an array or list. The linear search algorithm is used to iterate through every element in a list, then find and return the element if it is present. Read the complete article to understand Linear Searching in C better.

Table of Contents

What is Searching?

Searching is the method of fetching any desired element or information from a collection of elements, such as an array, linked list, etc. If we find the element, then we return the index, and searching is successful. But, if we do not find the element, then we return that the element is not present in the list. There are two major types of searching in C.

Linear Searching
Binary Searching

Also read: Keywords and Identifiers in C

Linear Search Algorithm in C

Linear searching in C is used to find an element inside a list sequentially. Hence, it is also known as a sequential search algorithm. This is the simplest and most naive method of searching. With the help of the Linear Search algorithm, we search for a desired element in the list. It will return the index of the element if it appears in the list. If the element is absent, it returns a negative result, say -1.

Working of Linear Search Algorithm in C

Linear Searching in C iterates through every element inside the list. It suppose that every element is a match for the desired element say Key. However, if the matching condition fails, it iterates forward and look at the next index until the element is found.

If the matching condition for any element matches, then the index of that element is returned. However, if the element is not present in the list, we return “Not Found”.

For example, consider an array, arr [ ] = { 20, 35, 40, 16, 23, 22, 40}. Suppose our desired element is key = 30.

Step 1: We start from the first element at arr[0] and compare the key present at arr [0].

If key == arr[0], but 30 is not equal to 20, hence this condition fails. Now, our pointer iterates one step ahead.

Step 2: Now, we compare our key element with the arr[1]. It is also not equal to our key element.

Step 3: Next, we compare elements at arr[2]. It is also not equal to our key element.

Step 4: We keep comparing elements until we reach the size of our array. If the element does not match any index, we keep iterating.

Step 5: When we check the element at arr[4], the element matches our key element. Now, we will return the index of the element.

Recommended Technical Course

Implementation of Linear Search Algorithm in C

Now, let us check the implementation of the linear search algorithm in c below.

Linear Search Algorithm in C

#include <stdio.h>

int linearSearch(int a[], int n, int val) {

for (int i = 0; i < n; i++)

{

if (a[i] == val)

return i+1;

}

return -1;

}

int main() {

int a[] = { 20, 35, 40, 16, 23, 22, 40}; // Array

int val = 30; Key Element

int n = sizeof(a) / sizeof(a[0]); // size of array

int res = linearSearch(a, n, val); // Store result

printf (“The elements of the array are – “);

for (int i = 0; i < n; i++)

printf(“%d “, a[i]);

printf(“\nElement to be searched is – %d”, val);

if (res == -1)

printf(“\nElement is not present in the array”);

else

printf(“\nElement is present at %d position of array”, res);

return 0;

}

Output

The elements of the array are 20, 35, 40, 16, 23, 22, 40

Element to be searched is 30

Element is present at 6 position of array.

Pseudocode of Linear Search Algorithm

Let us check the pseudocode for the Linear search algorithm in C.

Linear Search Algorithm in C Pseudocode

1. Start

2. linear_search ( array, value)

3. For each element in the array // loop the element till the size

4. If (searched element == value)

5. return key

6. end if

7. end for

8. end

Linear Search Algorithm Complexity

There are three main complexities in the Linear search algorithm in C. Check below.

Best Case: When the element we are searching for is present at the first index of the array or linked list, it is called the best case. It is in order of O(1).
Average case: This case occurs when the element we are searching for is present anywhere between the first and the last element of the array. The time complexity for this case is in order of O(N), where N is the length of the array.
Worst Case: This is the most critical case in the algorithm. Suppose the element we are searching for is found at the index. Then, the worst case happens. The time complexity for this case is O(N).

Space Complexity: The space complexity, also known as auxiliary space, is in the order of O(N), as we only need to iterate the list once without using any extra space or variable.

Also Read: What are Array in C

Advantages of Linear Search Algorithm

The linear search algorithm in C has the following benefits.

The linear search algorithm is simple and easy to use for small and simple applications.
This algorithm can be used without the need for any extra memory. Hence, it saves resources by not using any extra space.
This algorithm works best for small datasets.
This algorithm can be used for various data structures, such as arrays and linked lists, without modification.

Disadvantages of Linear Search Algorithm in C

The time complexity of the linear search algorithm is high O(N). We need to iterate through every element to find our key element.
It does not work well for extensive collections.
It is not suitable for sorted data. A binary search can better work on a sorted collection of data.

Applications of Linear Search Algorithm in C

Let us now know some of the significant uses of the Linear search algorithm.

It searches and returns the key elements in an array.
It works best when we are searching for an element which is stored in a contiguous memory location.
It can be used in an array of any dimension, such as 1-D or N-D arrays.
It can be used when the element in the array is very small.

Also read: 12 Best Full Stack Web Development Courses in India

FAQs

What is a linear search algorithm in C?

Ans: A Linear Search algorithm is used to find an element in an array sequentially.

What is the worst-case time complexity of the linear search algorithm?

Ans: The worst-case time complexity of a linear search algorithm is O(N).

Why is the linear search algorithm not preferred in sorted arrays?

Ans: A linear search algorithm iterates over all the element in the array to find the element. However, an optimal approach to using the Binary search can find the element in a time complexity of O(logN).