Linear Search Algorithm and Complexity Analysis

Linear Search (Sequential Search) searching ki sabse fundamental aur intuitive technique hai. Is algorithm me hum array ke pehle element (index 0) se start karke aage badhte hain aur har element ko target key value ke saath sequentially compare karte hain jab tak target element na mil jaye ya array khatam na ho jaye.

Key Features of Linear Search

• Array sorted hona zaroori nahi hai (yeh unsorted aur sorted dono data par kaam karta hai).
• Yeh random access (arrays) aur sequential access (linked lists) dono structures par execute ho sakta hai.
• Implementation bohot simple aur direct hota hai.

Target Key = 35
Array:  [ 12 | 45 | 78 | 35 | 90 | 22 ]
Index:     0    1    2    3    4    5

Step 1: Compare Key(35) == A[0](12) -> Mismatch, move right
Step 2: Compare Key(35) == A[1](45) -> Mismatch, move right
Step 3: Compare Key(35) == A[2](78) -> Mismatch, move right
Step 4: Compare Key(35) == A[3](35) -> Match Found at Index 3! Return 3.

Linear Search Algorithm

LINEAR_SEARCH(A, N, KEY)
1. Initialize i = 0
2. Repeat Step 3 while i < N:
3.     If A[i] == KEY then:
           Return i   [Element found at index i]
       Else:
           Set i = i + 1
4. [End of Loop]
5. Return -1          [Element not found in array]

Complexity Analysis

• Best-case Time: O(1) – Jab target key array ke first index A[0] par hi mil jaye (only 1 comparison).
• Worst-case Time: O(n) – Jab target key last index A[n-1] par ho ya array me present hi na ho (n comparisons).
• Average-case Time: O(n) – On average (n+1)/2 comparisons lagte hain.
• Space Complexity: O(1) auxiliary space (kisi extra memory ki requirement nahi hoti).

Agli post me hum cover karenge Binary Search Algorithm (Iterative and Recursive) jo sorted arrays par O(log n) time me search karta hai.