What is linear search?

Question

Accepted Answer

**Linear search** scans a collection element by element until it finds the target or reaches the end. It works on **any** list — sorted or not — but runs in **O(n)** time.

## The idea

No assumptions about order: just check each item one at a time.

## Example

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Complexity

- **Time:** O(n) worst case (target last or absent), O(1) best case.
- **Space:** O(1).

## When to use

- The data is **unsorted** and you cannot afford to sort it.
- The list is small, so O(n) is negligible.
- You need a one-off lookup where building an index or sorting first is not worth it.

If you search repeatedly, prefer a sorted array with binary search or a hash set for O(1) average lookups.

## Why it matters

Linear search is the baseline every other search is measured against.

It reminds you that the *right* algorithm depends on the data: unsorted and tiny favors the simple scan; large and repeatedly queried favors smarter structures.

Knowing when O(n) is good enough prevents premature optimization.