DSA Linear Search

DSA Linear Search – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

Linear Search is the simplest searching algorithm in Data Structures & Algorithms (DSA).
It checks each element one by one until the required value is found or the list ends.

1️⃣ What is Linear Search?

Linear Search:

Searches an element by scanning sequentially
Starts from the first element
Compares each element with the target value
Stops when:
- Element is found ✅
- Array ends ❌

📌 Also called Sequential Search.

2️⃣ Simple Idea (One Line)

Check every element until the value is found

3️⃣ When to Use Linear Search?

✔ Small datasets
✔ Unsorted arrays
✔ Simple implementation required
❌ Large datasets (slow)

4️⃣ Linear Search – Manual Run-Through

Given Array

Target Value

Step-by-Step Search

Step	Compared Value	Match?
1	10	❌
2	23	❌
3	45	❌
4	70	❌
5	11	❌
6	15	✅ Found

📌 Element 15 found at index 5.

5️⃣ Linear Search Algorithm (Steps)

Start
Take input array and target value
Compare target with each element from index 0
If match found → return index
If end reached → return not found
Stop

6️⃣ Pseudocode

7️⃣ Linear Search Implementation (C++)

#include <iostream>
using namespace std;

int main() {
int arr[] = {10, 23, 45, 70, 11, 15};
int n = 6;
int key = 15;

for(int i = 0; i < n; i++) {
if(arr[i] == key) {
cout << "Element found at index " << i;
return 0;
}
}

cout << "Element not found";
return 0;
}

#include <iostream>

using namespace std;

int main() {

int arr[] = {10, 23, 45, 70, 11, 15};

int n = 6;

int key = 15;

for(int i = 0; i < n; i++) {

if(arr[i] == key) {

cout << "Element found at index " << i;

return 0;

}

cout << "Element not found";

return 0;

}

Output

8️⃣ Time Complexity of Linear Search

Case	Condition	Time Complexity
Best Case	Element at first index	O(1)
Average Case	Element in middle	O(n)
Worst Case	Last index or not present	O(n)

📌 Must check all elements in worst case.

9️⃣ Space Complexity

Metric	Value
Extra Space	O(1)
Type	In-place

🔟 Advantages of Linear Search

✔ Very easy to understand
✔ Works on unsorted arrays
✔ No extra memory needed
✔ Useful for small lists

1️⃣1️⃣ Disadvantages of Linear Search

❌ Slow for large datasets
❌ Inefficient compared to Binary Search
❌ Repeated comparisons

1️⃣2️⃣ Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Data Order	Any	Must be sorted
Speed	Slow	Fast
Time Complexity	O(n)	O(log n)
Implementation	Easy	Moderate

Exam / Interview Questions (Linear Search)

Q1. Is Linear Search used on sorted arrays?
👉 Yes, but not efficient

Q2. Worst-case time complexity?
👉 O(n)

Q3. When should Linear Search be used?
👉 Small or unsorted datasets

Final Summary

✔ Linear Search checks elements one by one
✔ Simple and intuitive
✔ Works on any array
✔ Time Complexity: O(n)
✔ Space Complexity: O(1)
✔ Best for beginners and small datasets

DSA Linear Search