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 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 comparisons, return 3
First step
1
i=0: A[0]=4 vs 2, no.
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
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 in [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 in [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 in [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 in [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=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(nlogn)) then binary-search k times (O(klogn)). 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?