Introduction

The Linear Search algorithm is the simplest searching technique used to find an element in an array.

Given an array arr[] and a target element x, the task is to determine whether the target exists in the array and return its index.

Linear Search works by:

  • checking elements one by one
  • starting from the beginning
  • until the target is found

This problem helps in understanding:

  • array traversal
  • searching techniques
  • iteration logic
  • basic algorithm design

Example

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

Input: arr[] = [5,2,8,1]
x = 6
Output: -1
Explanation:
Element 6 does not exist in the array.

Constraints

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

Approach 1 : Linear Traversal

Explanation

The simplest way to solve this problem is:

  1. Traverse the array from beginning
  2. Compare every element with target
  3. If target matches:
    • return index
  4. Otherwise:
    • continue traversal

This approach works for:

  • sorted arrays
  • unsorted arrays

Steps

  1. Traverse the array.
  2. Compare current element with target.
  3. If match found:
    • return index
  4. If traversal ends:
    • return -1

Dry Run

Input Array:[4,7,1,9,3]
Target = 9

Traverse 4:
4 != 9

Traverse 7:
7 != 9

Traverse 1:
1 != 9

Traverse 9:
9 == 9

Element found at index 3
Return 3

Linear Search Code

Complexity Analysis

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

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Edge Cases

  1.  Element present at beginning
  2. Element present at end
  3. Element not present
  4. Array contains duplicate elements
  5. Array contains one element

Why This Problem is Important

This problem helps in understanding:

  1. Array traversal
  2. Searching techniques
  3. Iteration logic
  4. Basic algorithm structure
  5. Sequential access

It is one of the most fundamental searching problems in DSA.

Real-World Applications

Linear searching is used in:

  1. Small datasets
  2. Unsorted data searching
  3. Sequential access systems
  4. File scanning
  5. Simple lookup systems

Common Mistakes

  1. Forgetting break statement
  2. Incorrect index handling
  3. Returning wrong value
  4. Loop boundary mistakes

Interview Tips

Interviewers often expect:

  1. Correct traversal logic
  2. Proper index handling
  3. Time complexity explanation

Always explain why Linear Search works on both sorted and unsorted arrays.

Related Questions

  1. Binary Search
  2. Search Insert Position
  3. Find Minimum
  4. First Occurrence
  5. Last Occurrence

Final Takeaway

Linear Search is the simplest searching algorithm that teaches sequential traversal and basic search logic. Understanding this problem builds a strong foundation for advanced searching and traversal interview problems.