# 3.5 Linear Search

> Check every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).

Chapter: Simple Sorting & Searching · ~25 min · easy
URL: https://dsa.fetehadin.com/learn/linear-search

## Mental model

Looking for your friend in a queue of strangers, you walk from the front and check **each face** until you see them, or reach the end. That's linear (sequential) search.

### The algorithm

```text
for each index i from 0 to n-1:
    if a[i] == key: return i
return -1        (only after checking everything)
```

### Strengths and weaknesses

- ✅ Works on **unsorted** data and on **linked lists**.
- ✅ Dead simple, no preparation needed.
- ❌ Slow for big data: up to **n** comparisons.

If you'll search the same large array many times, it's worth sorting it **once** and using binary search after that.

## C++ code: linear-search.cpp

```cpp
#include <iostream>
using namespace std;

int linearSearch(const int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i;      // found: stop right away
    return -1;             // checked everything: not there
}

int main() {
    int a[] = {23, 7, 41, 15, 9, 32, 18};
    int n = 7;
    cout << "search 9  -> " << linearSearch(a, n, 9) << "\n";
    cout << "search 23 -> " << linearSearch(a, n, 23) << "\n";
    cout << "search 50 -> " << linearSearch(a, n, 50) << "\n";
}
```

Expected output:

```text
search 9  -> 4
search 23 -> 0
search 50 -> -1
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(1): key at index 0 |
| Average case (found) | (n + 1)/2 comparisons → O(n) |
| Worst case | O(n): last item or not present |
| Needs sorted data? | No |

Space: O(1)

On a linked list, linear search is the **only** option, because you can't jump to the middle.

## Videos

- [What is binary search](https://youtu.be/j5uXyPJ0Pew) (mycodeschool): Starts with linear search, then shows why binary search is a huge improvement.

## Exam lens

Likely questions:

- Write a linear search function that returns the index of the key or −1.
- What are the best, average and worst case complexities of linear search?
- When is linear search preferred over binary search?
- Modify linear search to return the index of the LAST occurrence.

Common mistakes:

- Returning `-1` inside the loop (in an `else`), which stops after checking only the first item.
- Looping with `i <= n`, one past the end.
- Forgetting that an unsorted array cannot use binary search.

## Quick check

1. What is wrong here?

```cpp
for (int i = 0; i < n; i++)
    if (a[i] == key) return i;
    else return -1;
```
   A. Nothing
   B. It only ever checks a[0]
   C. It loops forever
   D. It reads past the end
   Answer: B. Either branch returns on the first iteration. `return -1` belongs after the loop.

2. Linear search on 1000 items, key not present. Comparisons?
   A. 1
   B. 500
   C. 1000
   D. 10
   Answer: C. Every item must be checked.

3. Linear search is the better choice when…
   A. the data is huge and sorted
   B. the data is small or unsorted
   C. you search millions of times
   D. never
   Answer: B. Sorting first costs O(n log n). For a single search on unsorted data, just scan.

## Practice

**Trace by hand.** How many comparisons does linear search make on `[7, 2, 9, 4, 9, 1]` for keys 9, 1 and 5?

Solution:

- key 9: **3** (first occurrence at index 2)
- key 1: **6**
- key 5: **6** (not found)


**Implement it.** Write `countOccurrences(a, n, key)` and `lastIndexOf(a, n, key)`.

Hint: For lastIndexOf, loop backwards from `n - 1` and return the first match, or loop forwards and remember the latest match.

**Problems:**

- [Check If N and Its Double Exist](https://leetcode.com/problems/check-if-n-and-its-double-exist/) (easy). Hint: For each item, linearly search for its double (O(n²)). Then think about how a set makes it O(n).
- [Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/) (easy). Hint: A linear scan with a digit counter.

## Mastery checklist

- [ ] I can write linear search returning the index or −1.
- [ ] I can state its best, average and worst case.
- [ ] I can explain when linear search beats binary search.