Introduction

Linear Search is a searching technique used to find a target element in an array by checking each element one by one from the beginning.

Given an array arr[] of size n and a target element x, the task is to determine whether the target element is present in the array.

This is one of the most basic searching algorithms and helps in understanding array traversal, searching techniques, and conditional checking.

Example:

Input: arr[] = [4, 7, 1, 9, 3]Target = 9
Output: Element Found
Explanation:
9 is present at index 3.

Input: arr[] = [10, 20, 30, 40]
Target = 25
Output: Element Not Found
Explanation:
25 is not present in the array.

Constraints

 1 <= n <= 10^5-10^9 <= arr[i] <= 10^9
-10^9 <= target <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to search for an element is:

  1. Traverse the array from beginning to end.
  2. Compare each element with the target value.
  3. If the element matches:
    • return found
  4. Otherwise continue traversal.

This approach is simple and works for both sorted and unsorted arrays.

Steps

  1. Traverse the array from index 0.
  2. Compare each element with the target.
  3. If target is found:
    • return True
  4. If traversal completes:
    • return False

Dry Run

Input Array: [4, 7, 1, 9, 3]Target = 9
Traverse 4:
4 != 9
Continue searching
Traverse 7:
7 != 9
Continue searching
Traverse 1:
1 != 9
Continue searching
Traverse 9:
9 == 9
Target element found
Final Result: Element Found

Brute Force Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
In the worst case, every element may need to be checked.

Space Complexity: O(1)
Explanation:
No extra data structure is used.
Only a few variables are required.

Approach 2 : Optimized Solution (Early Termination)

Explanation

The traversal approach itself is the optimal solution for unsorted arrays because elements may appear anywhere in the array.

However, we can optimize slightly using early termination:

  • stop traversal immediately once the target element is found.

This avoids unnecessary comparisons.

Steps

  1. Traverse the array.
  2. Compare current element with target.
  3. If target is found:
    • immediately stop traversal
  4. Otherwise continue searching.
  5. If traversal completes:
    • return not found

Dry Run

Input Array: [10, 20, 30, 40]Target = 25
Traverse 10:
10 != 25
Continue searching
Traverse 20:
20 != 25
Continue searching
Traverse 30:
30 != 25
Continue searching
Traverse 40:
40 != 25
Continue searching
Target element not found
Final Result: Element Not Found

Optimized Approach

Complexity Analysis

Time Complexity: O(n)Explanation:
The array may need to be traversed completely.

Space Complexity: O(1)
Explanation:
Only constant extra space is used.

Edge Cases

  1. Array contains only one element
  2. Target element is at first position
  3. Target element is at last position
  4. Target element is not present
  5. Array contains duplicate elements

Why This Problem is Important

This problem helps in understanding:

  1. Searching techniques
  2. Array traversal
  3. Conditional checking
  4. Early termination
  5. Search optimization basics

It is one of the most important beginner-level searching problems.

Real-World Applications

Linear Search is used in:

  1. Small datasets
  2. Unsorted data searching
  3. Contact searching
  4. Simple lookup systems
  5. Sequential data processing

Common Mistakes

  1. Forgetting break statement
  2. Incorrect comparison condition
  3. Traversing beyond array bounds
  4. Not handling missing elements properly

Interview Tips

Interviewers often expect:

  1. Correct traversal logic
  2. Early termination optimization
  3. Proper handling of edge cases

Always explain why Linear Search works well for small or unsorted arrays.

Related Questions

  1. Binary Search
  2. Search Insert Position
  3. First Occurrence of Element
  4. Last Occurrence of Element
  5. Count Occurrences in Array

Final Takeaway

Linear Search is a fundamental searching algorithm that teaches traversal logic, conditional checking, and basic search optimization. Understanding this problem builds a strong foundation for advanced searching algorithms like Binary Search.