csmasters.dev

Linear Search Algorithm on 1D Arrays

A Linear Search (also called a sequential search) is an algorithm that inspects every element of a one-dimensional array one by one in sequence, starting from the first position (Index = 1), until either the target element is located or the entire array has been examined.

1. How Linear Search Works

Target: 42
Array: [ 17,  8,  42,  95,  31 ]
          ▲   ▲    ▲
          │   │    └─ Match found! Set Found <- TRUE, stop search.
          │   └────── Check Index 2 (8 != 42) -> Next
          └────────── Check Index 1 (17 != 42) -> Next

Operational Steps:

  1. Initialize Flag and Pointer:
  • Found <- FALSE (tracks whether the target item has been located).
  • FoundIndex <- -1 (records the index location where the target resides).
  • Index <- 1 (starting array index).
  1. Sequential Loop:
  • Repeat while Index <= MaxSize AND Found = FALSE.
  • If Array[Index] = Target, set Found <- TRUE and FoundIndex <- Index.
  • Always increment Index <- Index + 1 to advance to the next position.
  1. Post-Loop Verification:
  • Check IF Found = TRUE: output the index position.
  • ELSE: output a notification that the item was not present in the dataset.

2. Efficiency & Characteristics

Characteristic

Linear Search

Data Order Requirement

None: Operates effectively on completely unsorted data.

Best-Case Efficiency

$1$ comparison (target is at index 1).

Worst-Case Efficiency

$N$ comparisons (target is at the very last index or completely absent).

Average Comparisons

$\approx N / 2$ comparisons.

Suitability

Ideal for small lists or unsorted data where overhead of sorting would exceed search savings.

AI Socratic Tutor

All-Access
Sign in or create an account. AI Tutor is an All-Access benefit.
Sign Up

Need guidance? Ask a question or use the hint below.

AI Socratic Tutor is an All-Access Benefit

Unlock step-by-step Socratic hints, algorithm trace table walkthroughs, and error diagnostics for every Cambridge exercise.

View All-Access Plans

You're chatting with an AI tutor, not a person. AI can make mistakes, so double-check its answers.

Exercise:
Task 1 Task 2 Task 3

Exam-Style Question: Complete the Linear Search Control Logic

+35 XP

Complete the missing keywords and variable values in the Cambridge linear search template for an array of 50 integers:

PSEUDOCODE 
Found <- [Space 1]
Index <- 1
WHILE (Index <= 50) AND (Found = FALSE) DO
    IF Scores[Index] = Target THEN
        Found <- [Space 2]
        Location <- Index
    ENDIF
    Index <- Index + [Space 3]
ENDWHILE
Word Bank / Available Cards (Drag into spaces or tap to place)

All-Access Required

Interactive exercises for Module 2 and beyond require an active plan.

Unlock All-Access ($30/mo) Already subscribed? Sign in