sreejithmvarma.in

PCCST303 · Module 4: Sorting and Searching

Linear Search

Sorting rearranges data; searching finds a specific value within it. Linear search is the most basic method: check every element, one at a time, until the target is found or there's nothing left to check.

Algorithm

LINEAR_SEARCH(A, N, KEY)
// A is the array to search
// N is the number of elements in A
// KEY is the value being searched for
 
1. For i = 0 to N-1:
       If A[i] == KEY:
           Return i
2. Return NOT FOUND

Worked example

Searching for 37 in [29, 10, 14, 37, 14]:

Index
29
10
14
37
14
01234
↑i

A[0]=29 != 37, continue.

Index
29
10
14
37
14
01234
↑i

A[1]=10 != 37, continue.

Index
29
10
14
37
14
01234
↑i

A[2]=14 != 37, continue.

Index
29
10
14
37
14
01234
↑i

A[3]=37 == 37, found. Return index 3.

Why linear search doesn't need sorted data

Key Idea

Linear search makes no assumption about ordering: it simply checks each element in turn. This is both its main strength (works on any array, sorted or not) and its main weakness (can't skip anything, even when the data is sorted).

Complexity

CaseComplexity
Best (target at index 0)O(1)
AverageO(n)
Worst (target absent, or at the end)O(n)
SpaceO(1)

Quick recall

  • Checks elements one at a time from the start; works on unsorted data since it makes no ordering assumption.
  • O(1) best case, O(n) average/worst case, O(1) extra space.
  • The only search method covered that doesn't require the array to be sorted first.