AV
LibraryLinear Search

Linear Search

Easy

Linear 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

**Time Complexity**: O(n) - May need to check every element
**Space Complexity**: O(1) - Only needs to store a few variables

Best and Worst Cases

**Best Case**: O(1) - Element is at the first position
**Worst Case**: O(n) - Element is at the end or not present
**Average Case**: O(n) - On average need to check n/2 elements

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

**Small datasets**: Arrays with fewer than 100 elements
**Unsorted data**: When sorting cost outweighs search benefit
**Frequent insertions**: Data constantly changing
**Simple requirements**: When complexity is not a concern
**Linked lists**: When random access is not available

Comparison with Binary Search

Linear: O(n) for unsorted, O(n) even if sorted
Binary: O(log n) but requires sorted input
Break-even point around n = 64 for single search
If doing multiple searches, sorting becomes worthwhile

Real-world Applications

Searching small collections
Finding all matching items
Checking if item exists in small list
Initial implementation before optimization
Educational purposes

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;
}

Tags

searchingsimplebasicbeginner

Quick Stats

Difficulty:Easy
Type:Searching

Share