Linear Search

In the previous lessons, we focused on sorting algorithms that arrange data in a specific order.

Once data is stored or sorted, the next natural question is:

How do we find a specific element?

In this lesson, we begin our journey into searching algorithms with the most fundamental one — Linear Search.

What Is Searching?

Searching means finding whether a particular value exists in a collection, and if it exists, determining its position.

Examples from daily life:

• Searching a name in a contact list
• Finding a file in a folder
• Looking for a roll number in attendance

All of these tasks follow some form of searching logic.

Linear Search – Core Idea

Linear Search works in the simplest way possible.

It checks each element one by one from the beginning of the list until the target element is found or the list ends.

There is no assumption about ordering. The data can be sorted or unsorted.

How Linear Search Works (Step-by-Step)

Suppose we have the following list:

[12, 45, 23, 67, 34]

We want to search for the value 67.

The algorithm compares:

• 12 → not match
• 45 → not match
• 23 → not match
• 67 → match found

The search stops immediately after finding the match.

Linear Search Algorithm (Code)

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

numbers = [12, 45, 23, 67, 34]
result = linear_search(numbers, 67)

if result != -1:
    print("Element found at index", result)
else:
    print("Element not found")

This implementation returns the index of the element if found, otherwise it returns -1.

Time Complexity of Linear Search

The time complexity depends on where the target element is located.

Best case:

The element is found at the first position — O(1).

Worst case:

The element is at the end or not present at all — O(n).

Average case:

The element is found somewhere in the middle — O(n).

Why Linear Search Is Still Important

Even though Linear Search is slow for large datasets, it is still widely used.

Reasons:

• Works on unsorted data
• Very easy to implement
• No extra memory required

For small datasets, Linear Search is often the best choice.

Real-World Example

Imagine a teacher checking attendance from a printed list.

The teacher reads names one by one until the student’s name is found.

This is exactly how Linear Search works.

When NOT to Use Linear Search

Linear Search becomes inefficient when:

• The dataset is very large
• Searching happens frequently
• Data is already sorted

In such cases, more efficient algorithms like Binary Search are preferred.

Mini Practice

Think about this:

• Would Linear Search be good for searching in Google?
• Would it work for finding a word in a small paragraph?

Exercises

Quick Quiz

In the next lesson, we will improve search efficiency by learning Binary Search and understanding how sorting enables faster searching.