Linear Search in Data Structures

In this tutorial by GoNimbus, we’ll explore one of the most fundamental and easy-to-understand searching algorithms — Linear Search.

Linear Search, also known as Sequential Search, is the simplest method to find a specific element within a list or array. It checks each element one by one until the desired value is found or the list ends.

Even though it’s not the fastest method for large datasets, it’s an excellent starting point for understanding how searching algorithms work.

---

🧩 What is Linear Search?

Linear Search is a step-by-step searching algorithm that does not require the array to be sorted.

It simply begins at the first element and compares each item in the list to the target value until it finds a match. If no match is found, the algorithm returns -1 to indicate that the value does not exist in the array.

---

⚙️ How Linear Search Works

Here’s how Linear Search operates behind the scenes:

1. Start from the first element in the array.
2. Compare the element with the target value.
3. If both match, return the index position.
4. If not, move to the next element.
5. Continue until the element is found or the end of the array is reached.
6. If the value is not found in the entire array, return -1.

---

🧠 Example: Manual Step-by-Step Search

Let’s manually go through an example to see how Linear Search works.

Array: [12, 8, 9, 11, 5, 11]
Target: 11

Steps:

• Compare 12 with 11 → ❌ Not equal
• Compare 8 with 11 → ❌ Not equal
• Compare 9 with 11 → ❌ Not equal
• Compare 11 with 11 → ✅ Found at index 3

Linear Search stops immediately once it finds the target value at index 3.

---

💻 Implementation in Python

Here’s how we can implement Linear Search in Python:

def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
            return i   # Target found
    return -1  # Target not found

# Example usage
arr = [3, 7, 2, 9, 5]
targetVal = 9

result = linearSearch(arr, targetVal)
if result != -1:
    print(f"Value {targetVal} found at index {result}")
else:
    print(f"Value {targetVal} not found in the array")

Output:
Value 9 found at index 3

In this tutorial, you can see how Linear Search goes through each element until it finds a match — simple yet effective!

---

⏱️ Time Complexity Analysis

Let’s understand the efficiency of Linear Search:

Case	Description	Time Complexity
Best Case	Target found at the first index	O(1)
Average Case	Target found in the middle	O(n/2) ≈ O(n)
Worst Case	Target not found or at the end	O(n)

As we can see, the time increases linearly with the number of elements — hence the name Linear Search.

---

💾 Space Complexity

Linear Search requires only a few variables for indexing and comparisons, so its space complexity is O(1) — making it extremely memory efficient.

---

⚡ When to Use Linear Search

Linear Search is ideal when:

• The dataset is small or unsorted
• Simplicity and quick implementation matter more than speed
• You need to perform one-time searches on unsorted data

However, for large sorted datasets, faster algorithms like Binary Search are recommended.

---

🧭 Key Takeaways

• Linear Search checks each element sequentially.
• Works on both sorted and unsorted datasets.
• Time Complexity: O(n)
• Space Complexity: O(1)
• Perfect for beginners learning DSA concepts.

---

🚀 Conclusion

In this GoNimbus DSA tutorial, we learned how Linear Search works, how to implement it, and when to use it effectively.

Though Linear Search is not the fastest algorithm, it forms the foundation for understanding advanced searching algorithms like Binary Search, Jump Search, and Interpolation Search.

Continue your learning journey with GoNimbus DSA Tutorials to strengthen your problem-solving skills — one algorithm at a time!

---