Linear Search

Task: Find 23 in this unsorted array

Why we need Linear Search

Imagine you're looking for a specific book on a messy shelf.
You check each book one by one until you find the right one.
That's exactly how Linear Search works.

What is Linear Search?

Linear Search is a method to find an element in a list/array.
It checks each element sequentially until the target is found or the list ends.
Example: Searching for 25 in [10, 20, 25, 30].

Step-by-step process

Start at the first element
Compare it with the target value
If it matches → return index
If not → move to the next element
Continue until found or list ends

Example in code

C++

int linearSearch(int arr[], int n, int key) { for(int i = 0; i < n; i++) {    if(arr[i] == key) return i; // found } return -1; // not found}

Complexity

Case	Time	Why
Best case	O(1)	Target is the first element.
Worst case	O(n)	Target is last or not present.
Average case	O(n)	Roughly half the list checked.

Advantages

Simple to understand and implement.
Works on unsorted lists.
No extra memory required.

Limitations

Slow for large datasets.
Inefficient compared to algorithms like Binary Search.

🎯 Quick recap

Linear Search = check items one by one.
Easy but inefficient for big lists.
Complexity: O(n) in worst case.