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.

The Formula

O(n)

time complexity

When to use: Looking for your keys by checking every pocket and drawer in order.

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.

Looking for your keys by checking every pocket and drawer in order.

Formal View

Linear search iterates through

A[0], A[1], \ldots, 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.

Target 2 is at the last position: all 4 comparisons made before match at index 3

Answer

4\text{ comparisons, return }3

First step

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

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

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

medium

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.

Common Mistakes

Using linear search on large sorted datasets when binary search would be dramatically faster - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
Forgetting to handle the case where the element is not found, leading to index errors - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
Stopping at the first match when you need to find all occurrences of the target value - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
Using linear search from a keyword alone - Signal words like algorithm, search, sort only point to a possible model; the computing structure must match too.

Why This Formula Matters

Linear search works on any list regardless of order, making it the most universally applicable search algorithm. It serves as the baseline against which more efficient algorithms like binary search are measured.

Frequently Asked Questions

What is the Linear Search formula?

How do you use the Linear Search formula?

Looking for your keys by checking every pocket and drawer in order.

Why is the Linear Search formula important in CS Thinking?

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.

← Back to Linear Search See All Examples Practice Problems

Related Concepts

Searching Array Binary Search Algorithm Efficiency

Related Formulas

Binary Search Formula