01
Overview

Traversal and linear search — the building blocks.

Every array algorithm starts here: walk the elements, find what you need.

A traversal visits every element in order. A linear search traverses until a target is found, returning its index (or -1 when absent). The two patterns are inseparable: linear search is a traversal with an early-exit condition.

The -1 sentinel is the AP CSA convention for "not found". Returning 0 or throwing an exception are common but incorrect alternatives.

On the AP exam, linear search is the foundation for almost every array FRQ — and identifying when to use it is half the battle.

02
Core Concept

Walk until found; return index or -1.

Standard contract for AP CSA search methods.

Basic traversal

for (int i = 0; i < arr.length; i++) {
    // do something with arr[i]
}

Linear search

public int indexOf(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Returns as soon as found — no wasted iterations. Falls through to -1 if no match exists.

For String arrays

for (int i = 0; i < arr.length; i++) {
    if (arr[i].equals(target)) return i;
}

Use .equals() for Strings — never ==.

03
Key Vocabulary

Vocabulary for traversal and search.

Used in every array problem.

Vocabulary
  • Traversal — visiting every element in order.
  • Linear search — traversal with an early-exit on match.
  • Sentinel value — -1 for "not found".
  • Early return — exiting as soon as the answer is known.
  • Target — the value being searched for.
  • Best / worst case — 1 comparison vs n.
04
AP Exam Focus

How traversal and search are tested.

Return-on-found and -1 sentinel are core.

Exam Focus
  • Return as soon as found. Continuing wastes iterations and may overwrite the answer.
  • Return -1 on absence. The standard AP contract.
  • String comparison. Use .equals().
  • Loop bound. i < arr.length, never <=.
05
Worked Example

Find a target with early return.

Trace the loop and the fall-through.

Worked Example AP-style reasoning

Problem. Find target 7 in [3, 1, 7, 9, 5].

Trace. i=0 (3): no. i=1 (1): no. i=2 (7): match → return 2.

Answer: 2.

What if target were 8? All five iterations check; none match; falls through to return -1.

06
Common Mistakes

Traversal and search pitfalls.

Most break the contract.

Watch Out
  • Not returning when found. Loop continues and may not return at all.
  • Returning 0 on absence. 0 is a valid index — use -1.
  • Using == for Strings. Always .equals().
  • Off-by-one loop bound. i <= arr.length crashes.
07
Reference Table

Linear search at a glance.

The four-line contract.

Traversal & Search Reference

AP Quick Reference
LinePurposeAP Tip
Loop headerWalk every indexi < arr.length
Match checkCompare to target== for ints, .equals() for Strings.
Return insideExit on first matchReturns index.
Return outsideSentinel fall-throughAlways -1.
08
Practice Tip

How to lock in linear search.

The four-line contract is muscle memory.

Practice Strategy
  • MCQ Practice — verify the loop, the early return, and the -1 fall-through in every option.
  • Java Lab — write indexOf variants for int, double, String, and object types.
  • FRQ Practice — make linear search a helper method; build other logic on top.
09
Section · 09

Practice — attempt these now.

AP-style assessments aligned to this lesson. Time them.

All practice
FRQ Practice 30 min 18 marks Pending

AP CSA Unit 07 Topic 04 Array Traversal and Linear Search FRQ Practice

AP-style topic practice assessment

Start