Linear Search In C With Examples

In today’s programming world, and particularly with the rise of deep-learning algorithms, linear search is a must-learn for every programmer. This beginner-friendly tool opens up a new realm of possibilities for development and is very easy to understand!

Linear search is present in many modern programming projects, and we want you to learn the fundamentals so that after finishing this article, you can start playing with it in your projects.

By the way, even though we’ll be using C today, linear search is present in all programming languages, so feel free to translate the examples to the ones you dominate. Without further delay, let’s get started!

What is Linear Search?

A search algorithm checks if a specific element is present in some kind of data structure, such as an array or a list. If the desired element is there, then we can identify it and proceed with further logical operations. 

Search algorithms are broadly divided into two categories. Sequential search algorithms are the easiest, as they check every element of an array one after the other (like linear search). 

We also have interval search algorithms, designed for working with sorted data structures, and are faster and more efficient than sequential search algorithms. 

For example, binary search works by repeatedly dividing in half an array or some other type of data arrangement, until it finds its target.

Among the variety of search algorithms used in programming, linear search is one of the most useful. As you’ll learn in the next section, its usability-complexity ratio is through the roof. 

How Does Linear Search Work?

We now get the gist of what linear search does, but the truth is that we’ve only just scratched the surface. In this section, we’ll explain how this code’s syntax works so that you can get a more intuitive grasp of the inner workings of this algorithm.

To start using Linear Search, you must first input the element that will be searched. Then, starting from the first one, every element of a list will be checked using some kind of conditional.

If the element is found, then you can return its value and index position. If not, a “-1” return means that no element corresponds with the one we are looking for. Let’s see a quick example.

#include <stdio.h> 

int search(int arr[], int N, int x) 
{
     int i; 
     for (i = 0; i < N; i++) 
     if (arr[i] == x) 
     return i;
return -1; 
}

In the above example, first, we write the conditional that searches x in arr[]. If available, the conditional returns the index value, and if not, it returns -1. Now let’s build a functional example upon that.

Functional syntax example

We’ll add a second section to our example, and we want you to pay close attention to how they both relate.

#include <stdio.h> 

int search(int arr[], int N, int x) 
{
     int i; 
     for (i = 0; i < N; i++) 
     if (arr[i] == x) 
     return i;
 return -1; 
} 

int main(void) 
{ 
     int arr[] = { 2, 3, 4, 10, 40 }; 
     int x = 10; 
     int N = sizeof(arr) / sizeof(arr[0]); 
     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; 
}

Now we’ve expanded the functionality by adding another conditional section. In this section, we define the arr[] values, which number we want to find, and the array’s length. 

Finally, if the target value is found, we print it next to its corresponding index value. If not, we print a string informing that the target value can’t be found. Let’s look at the output of this code:

And now, let’s see what happens if we change our target value to the integer 2:

So, while you can obviously play with this second part of the code and make it print a different sentence, for the most part, it is that easy!

Time Complexity Explained

We mentioned before that interval search algorithms work faster and more efficiently than linear search. But, why is that? 

It all boils down to time complexity, meaning the time the search operation takes to finish. Time complexity will vary depending on the array’s length, and the kind of operation we are doing.

The logic of interval searches (which we’ll leave for another article) will always work faster. This means that while the time complexity of linear search (defined as O(n)) is slower than that of binary search, both will return the same values.

Using linear search in an ideal environment, we’ll find our target in the first position of the array, resulting in an O(1) time complexity. The worst-case scenario would result in a time complexity equal to the array’s length, meaning the target would be in the last position. 

You can see how if the position of our desired target can vary randomly, this makes linear search a very inefficient method.

You should understand by now that linear search isn’t ideal for working with large amounts of data. So, conversely, linear search is a great option when working with small data samples that demand a simple solution. 

What are the advantages of Linear Search?

Even if Linear Search is slower than other search algorithms, it does have certain boons that make it a unique option for programmers.

For example, Linear Search can be used with any kind of data collection. It doesn’t matter if it’s sorted or unsorted. It’s granted that Linear Search will find our target value, no matter how disorganized our collection is. 

Also, the target value can be any type of data, such as a string or a boolean. Let’s remember our code example:

#include <stdio.h> 
int search(int arr[], int N, int x) 
{
     int i; 
     for (i = 0; i < N; i++) 
     if (arr[i] == x) 
     return i;
     return -1; 
}

See how this logic applies to any array of data, even if it’s wholly unsorted and disorganized? The linear algorithm checks every possibility available in the collection until the element matches our target. Let’s redefine our array to be more random.

Even if our array was randomly organized, linear search would still find our target given enough time. Moreover, this same operation would be impossible using an interval search algorithm because it can’t work with unsorted data structures.

So, linear search is actually an exceptionally noble algorithm despite its apparent inefficiency. 

Conclusion: Linear Search In C With Examples

Let’s recap! We’ve learned what linear search is and what we can do with it. We’ve reviewed its foundational features with a huge code example. Also, we discussed its best uses and shortfalls.

We also delved a little into the concept of time complexity, how it works, and how it defines the efficiency of any search algorithm. Now, you can decide which search algorithm is best for your particular code.

We recommend that you keep these examples handy and check them whenever necessary. In fact, you can copy and paste our sample into a C interpreter and start playing with it right away. 

Remember that you can always use C’s official documentation as a reference in conjunction with any online resources you prefer.

The image featured at the top of this post is ©Gorodenkoff/Shutterstock.com.