Linear Search Examples in CS Thinking

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Linear Search.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in CS Thinking.

Concept Recap

A search algorithm that checks each element in a list one by one, starting from the first, until the target is found or the entire list has been examined. It is the simplest search algorithm and works on both sorted and unsorted data.

Looking for your keys by checking every pocket and drawer in order.

Read the full concept explanation →

How to Use These Examples

Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

Core idea: Simple but slow for large lists — must check up to every element in the worst case.

Common stuck point: Linear search works on any list; binary search is faster but requires sorted data.

Sense of Study hint: To implement linear search, start at index 0 and compare each element to the target. If a match is found, return that index. If you reach the end without finding a match, return -1 or a 'not found' indicator. No sorting or special preparation is needed.

Worked Examples

Example 1

medium

Trace: ```
for i = 0 to n-1:
if A[i] == target: return i
return -1
```
for

A = [4, 1, 7, 2]

, target

= 2

. Give the comparisons and return value.

Target 2 is at the last position: all 4 comparisons made before match at index 3

Answer

4\text{ comparisons, return }3

First step

i=0: A[0]=4 vs 2, no.

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

medium

Trace linear search of

[3, 8, 8, 1]

for

8

, first-match. Output the index and comparisons.

First-match search for 8: 3 checked first, then 8 found at index 1 after 2 comparisons

Example 3

hard

Sentinel linear search avoids checking the loop bound each iteration by appending the target to the end of the array. Briefly explain why this is correct.

Example 4

hard

Design a single linear pass over

[3, 1, 4, 1, 5, 9, 2, 6]

that returns the index of the FIRST element strictly greater than 5. Give the result.

Predicate search for first element > 5: indices 0-4 all fail, 9 at index 5 is the first match

Example 5

challenge

Self-organizing linear search moves a found element to the front. After many queries with skewed access (some keys queried far more often), why is amortized cost better than plain linear search?

Practice Problems

Try these problems on your own first, then open the solution to compare your method.

Example 1

easy

What is the time complexity of linear search?

Example 2

easy

Does linear search require the list to be sorted?

Example 3

easy

Linear search on

[4, 8, 15, 16]

for

15

finds it at which 0-indexed position?

Linear search for 15: scanned 4 and 8 before finding 15 at index 2

Example 4

easy

Worst case, how many elements does linear search check in a list of

50

Example 5

easy

In the best case, how many comparisons does linear search make?

Example 6

easy

Looking for your keys by checking every pocket in order is an analogy for which search?

Example 7

easy

If the target is not in the list, what should linear search return (commonly)?

Example 8

easy

On unsorted data, can you use binary search directly?

Example 9

medium

Linear search for

9

[2, 5, 9, 9, 1]

, finding the FIRST match. Which index and how many comparisons?

First match for 9 found at index 2 after 3 comparisons; search halts

Example 10

medium

To find ALL occurrences of

9

[2,9,1,9]

, why can't you stop at the first match?

Finding ALL occurrences of 9 requires scanning every element; both index 1 and index 3 are matches

Example 11

medium

On average, how many comparisons does linear search make for a present target in a list of

n

(uniformly random position)?

Example 12

medium

A list of

1000

items will be searched once. Is it worth sorting it first to binary-search?

Example 13

medium

Linear search returns the index of the first match but your code uses the result without checking for -1. What bug class is this?

Example 14

medium

Compare linear vs binary search on a sorted

n=256

list, worst case comparisons.

Example 15

medium

A streaming sensor feed of unknown length must be searched for the first reading above 100. Why is linear search the right choice?

Example 16

medium

Linear search for

6

[6, 2, 9, 4]

. Which index and how many comparisons?

Target 6 is at index 0: best case — found in 1 comparison

Example 17

medium

Linear search for

7

[1, 2, 3]

(not present). How many comparisons before returning not-found?

Searching for 7 (absent): all 3 elements checked, not-found returned after 3 comparisons

Example 18

challenge

For a single one-time lookup, prove linear search beats sort-then-binary-search asymptotically. State both costs.

Example 19

challenge

You search an unsorted list of

n

for a target known to appear exactly once. Give the exact expected number of comparisons and derive it.

Example 20

challenge

Design a single linear-search pass that finds BOTH the minimum and maximum of a list. How many comparisons, roughly, and why one pass suffices.

Example 21

easy

Linear search on

[7, 3, 9, 5]

for

9

: at which 0-indexed position is it found?

Linear search for 9: checked 7 and 3 first, then found 9 at index 2

Example 22

easy

True or False: linear search works on linked lists even though you can't index them in

O(1)

Example 23

easy

Linear search on

[10, 20, 30]

for

50

. What is the result?

Target 50 not in list: every element checked, returns not-found (−1)

Example 24

easy

Looking up a name in an unsorted contact list by scrolling top to bottom is an example of which algorithm?

Example 25

easy

Why might linear search outperform binary search on a list of size

4

Example 26

easy

Linear search on

[5, 5, 5, 5]

for

5

(first match). How many comparisons?

All elements are 5; first-match search hits index 0 immediately — 1 comparison

Example 27

medium

Linear search returns the index of the FIRST match. Modify the algorithm so it returns the index of the LAST match. What is the smallest change?

Example 28

medium

You need to COUNT how many times

5

appears in

[5, 2, 5, 1, 5, 3]

. Why can't you reuse plain linear search unchanged?

Counting all occurrences of 5: must visit every element; matches at indices 0, 2, and 4

Example 29

medium

A web-scraper reads pages from a never-ending RSS feed and stops at the first article matching a keyword. Why is linear search the natural fit?

Example 30

medium

Linear search a list of

n=2^{20}

. Approximate worst-case comparisons vs binary search on the SAME size sorted list.

Example 31

medium

A naive linear search uses `for i = 0 to n` (inclusive). What bug class does this typically produce?

Example 32

medium

You're given an unsorted list and asked to find the SMALLEST element. Is this a linear-search-style problem?

Example 33

medium

If you must perform

k = 100

searches on the SAME unsorted list of

n = 10{,}000

items, total work is approximately?

Example 34

hard

On a list of

n

items where the target is present with probability

p

(and at a uniform random position when present), what is the expected number of comparisons?

Example 35

hard

You sort first (

O(n \log n)

) then binary-search

k

times (

O(k \log n)

). For what

k

does this beat

k

linear searches (

O(kn)

Example 36

hard

Why is the FOR-loop version of linear search still

O(n)

even if you use SIMD/parallel comparisons that check 8 elements at a time?

Example 37

hard

You have an unsorted array of

n

pairs

(x, y)

and must find the pair whose

x

matches a query. After finding, you return `y`. Worst-case time and space?

Example 38

hard

On a list of

n

unique elements where the target is GUARANTEED present, what is the worst-case number of comparisons for linear search?

Example 39

challenge

Argue that any comparison-based search on an UNSORTED list of

n

items must take

\Omega(n)

time in the worst case.

Example 40

challenge

A list of

n

items is sorted, but a coworker calls plain linear search instead of binary search. Performance is

200{\times}

worse than expected at

n = 2^{20}

. Is that ratio plausible?

Example 41

challenge

You must check whether ANY of 5 targets appears in a list of

n

items. Best total cost using linear search?

← Back to Linear Search Formula Explained Practice Mode

Related Concepts

Searching Array Binary Search Algorithm Efficiency

Background Knowledge

These ideas may be useful before you work through the harder examples.

searchingarray