On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 6-8

Linear Search

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.

O(n) time complexity

Quick Answer

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. Use it when the list is unsorted, short, or searched only once, or when you need every match rather than just one. It needs no preparation and works on any data, but in the worst case it looks at every item: 500 checks for a list of 500. When it reaches the end without a match, it must report 'not found' clearly, for example by returning −1.

Why This Matters

Linear search is the method you can always fall back on: unsorted lists, lists that change constantly, searches by any property, such as the first student taller than 160 cm. Knowing its cost tells you when it stops being good enough: a million unsorted records can take a million comparisons. And a forgotten not-found case returns a wrong answer or crashes.

Intuitive Explanation

You are looking for the red marker in a box of 12 mixed markers. Nothing about the box helps, so you take them out one at a time: blue, green, black, red. Found on the 4th try. If the red one had been last you would have needed all 12, and if there were no red one you could only be sure after checking all 12. That is linear search: best case 1 check, worst case n checks, and on average about half.

As code it is a single loop over the indexes: for i from 0 to len(list) − 1, if list[i] equals the target, return i. Only when the loop finishes without returning do you know the target is missing, so the 'not found' result goes after the loop, never inside it. Searching [56, 12, 37, 5, 23] for 5 checks 56, 12 and 37, then finds 5 at index 3 on the 4th check. Searching it for 40 checks all 5 items and then returns −1.

Linear search is not always the slow choice. Binary search needs sorted data, and sorting first costs far more than one linear search. But on a large sorted list that is searched again and again, linear search wastes effort: a sorted list of 1,000 needs up to 1,000 linear checks but at most 10 binary ones. And when you need all the matches, say every 7 in a list, linear search must not stop at the first one; it keeps going to the end.

Think of it like this. 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.

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


When to Use

Use linear search when the data is unsorted, the list is short, you search it only once, or you need every match. It also works when you search by something the list is not sorted by, such as the first score above 90 in a list sorted by name. If the data is sorted and you will search it many times, binary search is far faster. If the job is to put the list in order, that is Sorting.

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

How to Recognize It

Before choosing linear search, look at whether the data has any order that would let you skip items.

  1. Is the list in no useful order for the value you want?

    Yes leaves linear search as the safe choice. If it is sorted by that value and you can jump to the middle, Binary Search is far faster.

  2. Do you need every match, such as all students named Sam, not just the first?

    Yes means a full pass that keeps going after each match. If you only need to know whether one exists, stop at the first hit; both are still linear search.

  3. Is the answer a position or 'not found', rather than the list put in order?

    Yes is searching. If the result is the whole list rearranged, the question is about Sorting.

  4. Is the question about this one-by-one way of looking, not about loops in general?

    Yes is linear search. If it asks how a loop repeats or when it stops, for any purpose, the topic is Iteration.

Linear Search vs Binary Search vs Searching vs Iteration

Linear search is one kind of searching, it competes with binary search, and its code is a simple loop. Ask whether the question is about this method, a faster rival, searching in general, or repeating steps.

Linear Search

Meaning
Linear search looks at each item in turn, from the first, until it finds the target or runs out of items.
Key test
No order needed; up to one check per item.
Formula
worst case=n checks
Example
Looking for a red sock by pulling socks out of a drawer one at a time.

Binary Search

Meaning
Binary search finds a target in sorted data by checking the middle and discarding the half that cannot contain it.
Key test
Needs sorted data; each check removes half of what is left.
Formula
O(log⁡n)
Example
Finding page 300 in a 600-page book by opening the middle and halving.

Searching

Meaning
Searching is the general task of finding a value in a collection or reporting that it is not there.
Key test
The task is named but no method is chosen yet.
Example
Finding out whether 'banana' is on the shopping list.

Iteration

Meaning
Iteration is repeating a block of instructions until a stopping condition is met.
Key test
It is about any repeated step, not specifically looking for a target.
Example
A loop that adds up all the numbers from 1 to 50.

Formula & Notation

O(n) time complexity
Linear search iterates through A[0],A[1],…,A[n−1], returning the first index i where A[i]=t. Worst case: n comparisons (O(n)). Best case: 1 comparison (O(1)). Average: n/2 comparisons.

Worked Examples

Example 1 — Count the checks

Easy

Search the list [14, 3, 27, 8, 19, 3] for 8, then for 3, then for 30. For each, give the index returned and the number of checks.
Show the steps and the answer
  1. Search for 8: check index 0 (14), 1 (3), 2 (27), 3 (8). Match at index 3 after 4 checks.

    The loop goes in order and stops at the first match.

  2. Search for 3: index 0 holds 14, index 1 holds 3. Match at index 1 after 2 checks.

    There is another 3 at index 5, but this search asks for one position, so it stops at the first.

  3. Search for 30: check all 6 items, find no match, and return −1 after the loop.

    Only after the last item can the search be sure 30 is missing; −1 can never be a real index, so it clearly means 'not found'.

Answer: 8 → index 3 (4 checks); 3 → index 1 (2 checks); 30 → −1, not found (6 checks).

Takeaway: Finding an item at index i costs i + 1 checks; a missing item always costs a check of every element.

Example 2 — Sorted, but by the wrong thing

Standard

A class list is sorted alphabetically: (Ana, 78), (Ben, 93), (Cara, 85), (Dev, 97), (Eli, 88). Can binary search find the first student in the list who scored above 90? Which method works, and what is the answer?
Show the steps and the answer
  1. Check what the list is sorted by: names, A to Z. The scores 78, 93, 85, 97, 88 follow no order.

    Binary search needs order in the value being searched, and here the order is in the names, not the scores.

  2. Try the middle anyway: index 2 is Cara with 85. Scores above 90 sit on both sides, Ben (93) on the left and Dev (97) on the right.

    There is no safe half to discard, so halving could throw away an answer.

  3. Use linear search on the scores: Ana 78, no; Ben 93, yes. Stop after 2 checks.

    Checking in list order finds the first qualifying student in that order.

Answer: Linear search: Ben (93), found after 2 checks. Binary search does not apply, because the list is sorted by name, not by score.

Takeaway: Binary search needs data sorted by the very value you are searching for. Sorted by anything else, use linear search.

Example 3 — Find the mistake: 'not found' too early

Application

Pia writes: for i from 0 to len(list) − 1: if list[i] == target, return i; else return −1. Searching [6, 2, 9] for 9 gives −1, and she says: "9 must not be in the list." Find the mistake and correct it.
Show the steps and the answer
  1. Trace: i = 0, list[0] = 6 is not 9, so the else branch runs and returns −1 at once.

    A return ends the whole function, so the loop never reaches index 1 or 2.

  2. Spot the flaw: one mismatch was treated as proof that the target is missing.

    An item that does not match says nothing about the items not yet checked.

  3. Move return −1 below the loop, so it runs only after every item has been checked.

    'Not found' is a statement about the whole list, so it can only come at the end.

  4. Re-trace: 6 no, 2 no, 9 yes, so it returns 2 after 3 checks. Searching for 4 checks all 3 items, then returns −1.

    A target that is present and one that is missing now both get the right answer.

Answer: Put return −1 after the loop. The search for 9 then returns index 2.

Takeaway: Return 'found' inside the loop, but 'not found' only after the loop has finished.

Where You'll See It

  • Looking for your keys

    You check every pocket and drawer one by one until you find the keys or run out of places to look, which is exactly linear search over an unsorted set of spots.

  • Finding a friend in an unsorted photo roll

    If photos aren't organized, you scroll through them one at a time from the start until you spot your friend, because there's no order to let you jump ahead.

  • Reading a class roster top to bottom

    To find one student on an unalphabetized handout, you read name by name from the top; in the worst case the student is last and you check everyone.

Common Mistakes

  1. The slip: Linear search is the best choice because it always works.

    Why it's tempting: It works on any list, sorted or not, so it feels safest.

    Instead: Linear search is O(n); on large sorted data, binary search (O(log⁡n)) is dramatically faster. Use the sorted structure when you have it.

  2. The slip: Once I find a match I'm always done.

    Why it's tempting: Finding the target is usually the whole goal, so stopping feels complete.

    Instead: Stop at the first match only when you need one occurrence. To find all occurrences, keep scanning the rest of the list.

  3. The slip: If the item isn't in the list, the loop just handles it on its own.

    Why it's tempting: When nothing matches, it seems like there's nothing special to do.

    Instead: You must explicitly handle the not-found case (finish the whole list and return a clear 'not found'); ignoring it leads to index errors or wrong returns.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Linear search for 7 in [4, 9, 7, 2, 7]. Which index is returned, and how many comparisons are made?

    Hint: Check from index 0 and stop at the first match.

  2. Linear search for 5 in [4, 9, 7, 2, 7]. What does it return, and how many comparisons does it make?

    Hint: The search can only report 'not found' after checking everything.

  3. Find every index where 7 appears in [7, 3, 7, 1, 7, 8]. How many elements must you check?

    Hint: To find all matches, do not stop at the first one.

  4. A list holds 250 names. What is the worst-case number of comparisons for linear search? If the name is present and equally likely to be anywhere, what is the average?

    Hint: Worst case: the name is last or missing. What is the average of positions 1 to 250?

  5. A dictionary app stores 100,000 words in alphabetical order and runs thousands of searches a day. Linear search or binary search?

    Hint: Is the data sorted? Compare the checks each method needs.

  6. A student's linear search is 'for i in range(len(names)): if names[i] == target: return i'. They say: 'I don't need anything after the loop.' What happens when the target is missing?

    Hint: What does the function give back if the loop finishes without a match?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

If binary search is so much faster, why does anyone use linear search?

Because binary search needs sorted data, and sorting costs time. If you search an unsorted list of 1,000 items only once, a linear search takes at most 1,000 checks, while sorting first takes roughly 10,000 comparisons before binary search even begins. Linear search also wins on very short lists, where setting up any cleverer method is not worth the effort.

Does it help to put the most-searched items at the front?

Yes. Linear search stops at the first match, so items near the front are found fastest. Some programs move an item one step forward each time it is found, so popular items drift to the front over time. Your phone's recent-calls list works on a similar idea: the people you call most are usually near the top, so you rarely scroll far.

What is the average number of checks for a linear search?

If the target is in the list and every position is equally likely, you check about half the list on average: (n+1)/2(n + 1)/2 checks, so 50.5 for a list of 100. If the target is missing, you always check all nn items, because only reaching the end proves it is not there. That is why searches for missing items are the slowest case.

Learning Path

← Before

SearchingArray
Linear Search

You are here

You need Searching (finding a target and reporting 'not found') and Array (values reached by index) first. Linear Search adds the simplest complete method: one loop, one check per item, and a not-found result after the loop. Next, Binary Search shows how sorted data cuts the work to about log⁡2n checks, and Algorithm Efficiency describes linear search's cost as O(n).

See Also