Summary

Linear search looks for a value by checking each item in a list one by one, from start to end. The moment it finds a match, it stops and returns the position. If it reaches the end without a match, the value is not there. It is simple and works on any list, sorted or not.

Linear search is the first search algorithm almost everyone learns. And it is the one you already do in real life. Looking for your keys by checking one pocket at a time is linear search.

It is simple on purpose. But there is a smart way to think about it, and one moment where it quietly beats the fancier search everyone rushes to use. Let me walk you through it.

Linear search is a way to find a value in a list by checking every item in order. You start at the first item and compare it to what you want. If it matches, you are done. If not, you move to the next item and try again.

You keep going until you find the value or run out of items. That is it. There is no clever trick and no setup needed. This is one of the first algorithms covered in any DSA learning path, because it teaches the basic shape of searching.

The big upside is that linear search works on any list. The items can be in any order. They do not need to be sorted, which is not true of the faster search methods.

How does linear search work step by step?

Reading the idea is one thing. Watching the scan move is another. So let’s run linear search on a real list.

Take the array [4, 2, 7, 1, 9] and say you are looking for the value 7.

The search starts at the first spot, index 0. The value there is 4. That is not 7, so it moves on. Index 1 holds 2, still not 7, so it keeps going. Index 2 holds 7. That is a match, so the search stops right away and reports position 2.

Notice it never looked at the last two items. The moment it found 7, the work was done. This early stop is the key to how linear search behaves, and it is why the speed depends on where the value sits.

Now picture a value that is not in the list, like 5. The search would check all five items, find no match, and report that the value is missing. That is the slow case, because it touches everything.

Linear search code in Python and C++

The code is short and matches the idea exactly. Loop through the list, and return the position as soon as you find the value. Here it is in Python.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

The return inside the loop is the early stop. The final return of -1 means the value was never found. Here is the same logic in C++, the language most Indian placement tests expect.

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

Both versions do the same thing. Walk the list once, stop at the first match, and signal -1 when there is nothing to find. If you need every match instead of just the first, you skip the early return and collect each matching position as you go.

What is the time and space complexity of linear search?

The time depends on where the value sits. In the best case the value is the very first item, so the search ends in one step. That is O(1). In the worst case the value is last or missing, so the search checks every item. That is O(n). On average, it lands somewhere in the middle.

So we call linear search an O(n) algorithm, because we plan for the worst case. For a list of 1,000 items, that means up to 1,000 checks. A list of a million items means up to a million checks. The cost grows in a straight line with the list size, which is exactly where the name comes from.

Space is the easy part. Linear search needs no extra memory beyond a counter, so its space complexity is O(1). You can read the formal definition on Wikipedia’s linear search page.

A trick worth knowing

There is a faster version called sentinel search. You place the value you want at the very end of the list first. Now the search is guaranteed to find it, so you can drop the check that asks “have I run off the end of the list” on every step. That removes one comparison per item. It does not change the O(n) speed, but it does make each step a little lighter, which matters on huge lists.

When should you use linear search?

Use linear search when your data is not sorted. This is its real strength. Faster searches need the list in order first, and sorting takes time. If you only need to find one thing once, sorting first and then searching is often slower than just scanning.

It also shines on small lists. For a handful of items the speed difference does not matter, and the simple code is easier to read and harder to get wrong. Many real programs use linear search for short lists for exactly this reason.

Where it struggles is large, sorted data that you search again and again. There, the time you spend scanning adds up fast, and a smarter search pays off.

Linear search vs binary search

Binary search is the famous faster option, but it comes with a condition. The list must be sorted. When it is, binary search cuts the list in half each step, so it finds a value in a sorted list of a million items in about twenty checks, not a million. For the full walkthrough, read our binary search guide. The honest takeaway is simple. Sorted data that you search often calls for binary search. Unsorted data or a one-time lookup calls for linear search. You can compare both against the wider picture in our guide to data structures and algorithms.

FAQ

What is the time complexity of linear search?

O(n) in the worst case, because it may check every item. The best case is O(1) when the value is first. Space is O(1), since it needs no extra memory.

Does linear search need a sorted list?

No. That is its main advantage. Linear search works on data in any order, while binary search only works on sorted data.

Is linear search slower than binary search?

On large sorted lists, yes. Binary search is much faster there. But on unsorted data or very small lists, linear search is often the better and simpler choice.

When is linear search a good choice?

When the data is unsorted, when the list is small, or when you only need to search once. In those cases the cost of sorting first is not worth it.

What does linear search return when the value is missing?

Usually -1, or some signal that means not found. The code checks the whole list, finds no match, and reports that the value is not there.

Can linear search find more than one match?

Yes. Instead of stopping at the first match, you keep scanning to the end and collect every position where the value appears.

So what should you remember?

Linear search is the honest workhorse. Check each item in turn, stop the moment you find what you want, and report nothing if you reach the end empty handed.

It is not the fastest on big sorted lists. But on messy, unsorted, or small data, it is often the smartest pick. Knowing when to use it is worth more than knowing a flashier algorithm.

Now try it yourself. In the array [8, 3, 5, 9, 1], how many checks does linear search make to find 9?