Linear Search Examples: 46 Problems with Answers

Worked examples of Linear Search to try before you open each solution, then practice problems with answers.

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.
Show solution

Answer

4 comparisons, return 3

First step

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

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

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
Trace linear search of [3,8,8,1] for 8, first-match. Output the index and 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.

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 each one, 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?

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 in [2,5,9,9,1], finding the FIRST match. Which index and how many comparisons?

Example 10

medium
To find ALL occurrences of 9 in [2,9,1,9], why can't you stop at the first match?

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 in [6,2,9,4]. Which index and how many comparisons?

Example 17

medium
Linear search for 7 in [1,2,3] (not present). How many comparisons before returning not-found?

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?

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?

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?

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?

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=220. 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(nlog⁡n)) then binary-search k times (O(klog⁡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 Ω(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× worse than expected at n=220. 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?

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.

Ask yourself: Must you find a target by checking items one at a time, because the data is unsorted or searched only once?

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.

Linear search is reading down a printed sign-up sheet to find a name: start at the top, read each name, stop when you see it. You never skip ahead, because the sheet gives no clue where the name might be. Reaching the bottom without seeing it is the only way to be sure the name is not there.

Read the full lesson on Linear Search

Background knowledge

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

searchingarray