Linear Search

You have an array. Somewhere inside it sits a number you want. The question is simple. Where is it? At which position does it live? Linear search is the most basic way to answer that.

So let me say what it is in one line. Linear search means you walk through the array one element at a time. You start at the front. You check each one against the target. You stop when you find it or when you run out of elements.

That’s it. No tricks. You look at the first item. Is it the one? No. Move to the next. Is it the one? No. You keep going. The moment one matches, you stop and report where you found it.

🛒 A Real-World Way to Picture It

Think about looking for a friend in a queue at a movie hall. You don’t know where they are standing. So you start from the front. You check the first person. Not them. Second person. Not them. You keep walking down the line until you spot your friend.

That is exactly linear search. You go person by person. You stop when you find the right face. And if you reach the end of the queue without finding them, then your friend isn’t there.

🤔 What Are We Actually Doing?

Here is the problem we are solving. You have a bunch of values sitting in an array. You want to know if a certain value is present. And if it is, you want to know at which index.

Linear search answers both of these:

• Is the target in the array at all?
• If it is, what is its index? That is, its position.

The nice thing is linear search does not care about order. The array can be sorted. The array can be a complete mess. Linear search works on any array, sorted or not. You are just checking elements one by one. So order never matters.

We will write a function called linearSearch(arr, target). It returns the index where the target is found. If the target is not there, it returns -1. That -1 is just a signal. It means “not found”. We use it because a real index can never be negative.

📋 The Cases to Think About

Before writing code, look at the two things that can happen:

• Found case: the target matches some element. We return that element’s index right away and stop.
• Not found case: we reach the end and nothing matched. We return -1.

🪜 Steps to Do a Linear Search

Let’s lay out the plan in plain steps before any code. We have an array arr and a value target.

1. Start at the first index. That is index 0.
2. Compare the element at the current index with target.
3. If they are equal, you found it. Return the current index and stop.
4. If they are not equal, move to the next index.
5. Repeat steps 2 to 4 until you reach the end of the array.
6. If the loop ends and nothing matched, return -1.

Now let’s turn those steps into real code. We will run two searches. One for a value that exists. One for a value that does not. That way you can see both outcomes.

💻 Linear Search in Code

Here is linearSearch in all five languages. The array is the same in each. We search for 30, which is present. Then we search for 100, which is not.

#include <stdio.h>

// Returns the index of target in arr, or -1 if not found
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {   // walk from the first index
        if (arr[i] == target) {     // is this the one?
            return i;               // found it, send back the index
        }
    }
    return -1;                      // reached the end, not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Index of 30: %d\n", linearSearch(arr, n, 30));
    printf("Index of 100: %d\n", linearSearch(arr, n, 100));
    return 0;
}

Index of 30: 2
Index of 100: -1

#include <iostream>
#include <vector>
using namespace std;

// Returns the index of target in arr, or -1 if not found
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {  // walk from the first index
        if (arr[i] == target) {                  // is this the one?
            return i;                            // found it, send back the index
        }
    }
    return -1;                                   // reached the end, not found
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50};

    cout << "Index of 30: " << linearSearch(arr, 30) << endl;
    cout << "Index of 100: " << linearSearch(arr, 100) << endl;
    return 0;
}

Index of 30: 2
Index of 100: -1

public class LinearSearch {

    // Returns the index of target in arr, or -1 if not found
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {  // walk from the first index
            if (arr[i] == target) {             // is this the one?
                return i;                       // found it, send back the index
            }
        }
        return -1;                              // reached the end, not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        System.out.println("Index of 30: " + linearSearch(arr, 30));
        System.out.println("Index of 100: " + linearSearch(arr, 100));
    }
}

Index of 30: 2
Index of 100: -1

# Returns the index of target in arr, or -1 if not found
def linear_search(arr, target):
    for i in range(len(arr)):   # walk from the first index
        if arr[i] == target:    # is this the one?
            return i            # found it, send back the index
    return -1                   # reached the end, not found


arr = [10, 20, 30, 40, 50]

print("Index of 30:", linear_search(arr, 30))
print("Index of 100:", linear_search(arr, 100))

Index of 30: 2
Index of 100: -1

// Returns the index of target in arr, or -1 if not found
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {  // walk from the first index
    if (arr[i] === target) {              // is this the one?
      return i;                           // found it, send back the index
    }
  }
  return -1;                              // reached the end, not found
}

const arr = [10, 20, 30, 40, 50];

console.log("Index of 30:", linearSearch(arr, 30));
console.log("Index of 100:", linearSearch(arr, 100));

Index of 30: 2
Index of 100: -1

See how 30 sits at index 2. So the function gives back 2. And 100 is nowhere in the array. So it gives back -1. The same simple loop handles both cases.

⏱️ How Fast Is It?

Let’s talk about cost. How much work does linear search do?

In the worst case, the target sits at the very last position. Or it is not in the array at all. Then you have to check every single element before you know the answer. So for an array of n elements, you may do up to n comparisons.

Here is the full picture in a table.

🐢 Simple, but Slow for Big Data

Linear search is the easiest search to write and understand. For a small array, it is perfectly fine and fast enough.

But think about a list with a million elements. If the target is near the end, you check almost a million items one by one. That is a lot of work. Linear search does not scale well for large data. The work grows with the size of the list.

This is the exact pain that pushes us toward a smarter method. If your array is already sorted, you can throw away half the list with each check. You no longer step through one by one. That smarter method is binary search. It is far faster on big sorted data.

⚠️ Common Mistakes to Avoid

These small mistakes are common for beginners. Watch for these:

• Returning 0 instead of -1 for “not found”. Remember, 0 is a valid index. It means the first element. Use -1 for not found.
• Using = instead of == in the comparison. A single = assigns a value. But == checks if two values are equal. You want ==.
• Looping one step too far, like going to index n when the last valid index is n - 1. That reads past the end of the array.
• Thinking you need a sorted array. You don’t. Linear search works on any array. Sorting is only needed for faster searches like binary search.

🧩 What You’ve Learned

✅ Linear search checks elements one by one from the start until it finds the target or reaches the end.

✅ It returns the index of the first match, or -1 when the value is not present.

✅ It works on any array, sorted or not, because order does not matter to it.

✅ Its time complexity is O(n) and its space complexity is O(1).

✅ It is simple but slow for large data, which is why sorted data calls for binary search instead.

🚀 What’s Next?

• Binary Search
• Array Traversal