Unit 4 Cycle 2 Day 21: 2D Array: Linear Search
Share
2D Array: Linear Search
Section 4.11 — 2D Array Algorithms
Key Concept
Linear search in a 2D array checks every element using nested loops. For row-major search, the outer loop iterates over rows and the inner loop iterates over columns, returning the position when the target is found. The method can return a row-column pair, a boolean, or the value itself. On the AP exam, 2D linear search may early-return when the target is found or may continue to count all occurrences. The worst case checks all rows * columns elements.
Consider the following method.
For grid = {{5,3},{9,7}}, what does find(grid, 9) return?
Answer: (B) {1, 0}
9 is at grid[1][0] (row 1, column 0). Returns {1, 0}.
Why Not the Others?
(A) grid[0][0]=5.
(C) grid[0][1]=3.
(D) grid[1][1]=7.
Common Mistake
2D search returns {row, col}. Nested loops with early return for efficiency.
AP Exam Tip
Searching 2D arrays: return both row and column. Use early return when found.