Linear Search
EasyLinear Search is a basic search algorithm that checks every element in the list sequentially until the target is found or the list is exhausted. Works on both sorted and unsorted arrays.
Time Complexity
O(n)Space Complexity
O(1)Category
Searching
Introduction to Linear Search
Linear Search is the simplest search algorithm, often used as the starting point for learning about searching. Despite its simplicity, it remains useful in many practical scenarios, especially for small datasets or unsorted data.
How It Works
Linear Search is straightforward:
1. Start at the first element
2. Compare it with the target value
3. If it matches, return the index
4. If not, move to the next element
5. Repeat until found or end of array
Algorithm Complexity
Best and Worst Cases
Advantages
1. Simple to understand and implement
2. Works on unsorted arrays
3. No preprocessing needed
4. Useful for small datasets
5. Optimal for finding multiple occurrences
6. Cache-friendly for sequential access
Disadvantages
1. Very slow for large datasets - O(n) is inefficient
2. Inefficient compared to binary search on sorted data
3. Always checks every element (even if found early)
4. Not practical for real-time systems with large data
When to Use
Comparison with Binary Search
Real-world Applications
Optimization Techniques
1. **Sentinel Search**: Add target at end to reduce comparisons
2. **Jump Search**: Skip some elements for faster searching
3. **Fibonacci Search**: Non-uniform jumping pattern
Key Takeaways
- Works on unsorted arrays
- Sequential traversal
- Simple implementation
- Optimal for small datasets
- No preprocessing needed
- Rarely used for large data
Implementation
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}