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
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
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
Worked examples
Example 1
mediumfor i = 0 to n-1:
if A[i] == target: return i
return -1
```
for , target . Give the comparisons and return value.
Show solution
Answer
First step
See the full worked solution + why-it-works coaching
SetupKey insightWhy it worksCommon pitfallConnection
Example 2
mediumExample 3
hardCommon 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.