Linear Search Formula

Linear search is 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.

The Formula

O(n) time complexity

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

Quick example

Find 37 in [56,12,37,5,23]: check 56 (no), 12 (no), 37 (yes) — found in 3 steps.

What this formula means

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.

Formal view

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

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.

Common mistakes

  • Using linear search on large sorted datasets when binary search would be dramatically faster
  • Forgetting to handle the case where the element is not found, leading to index errors
  • Stopping at the first match when you need to find all occurrences of the target value

Why this formula 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.

Frequently asked questions

What is the Linear Search formula?

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.

How do you use the Linear Search formula?

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.

Why is the Linear Search formula important in CS Thinking?

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.

What do students get wrong about Linear Search?

Linear search works on any list; binary search is faster but requires sorted data.

What should I learn before the Linear Search formula?

Before studying the Linear Search formula, you should understand: searching, array.