Linear Search Algorithm in AP Computer Science A

In AP Computer Science A, a linear search algorithm is a standard algorithm that checks each element of an array or ArrayList in order, starting from either end, until it finds the target value or has checked every element. It typically returns the matching index, or -1 if the value isn't found.

What is Linear Search Algorithm?

A linear search is the most straightforward way to find something in a collection. You start at one end and check every element, one at a time, until you either find the target value or run out of elements. Think of it as flipping through a stack of papers one sheet at a time looking for your name. It's slow if the stack is huge, but it always works, and the stack doesn't need to be in any order.

The CED (EK 4.14.A.1) calls linear search a standard algorithm that works on both arrays and ArrayLists. It also points out that the search can begin from either end. A loop going from index 0 up to length - 1 works, and so does one going from the last index down to 0. The usual Java version uses a for loop, compares each element to the target, and returns the index as soon as there's a match. If the loop finishes without a match, the method returns -1, a value that can't be a real index. For 2D arrays (EK 4.14.A.2), you access each row and then run a linear search across that row. In practice, that means a nested loop.

Why Linear Search Algorithm matters in AP® Computer Science A

Linear search lives in Topic 4.14 Searching in Unit 4: Data Collections. It directly supports learning objective AP Comp Sci A 4.14.A, which asks you to develop code for linear search and to determine the results of executing a search. Those are two different skills. You need to be able to write the algorithm yourself, and you need to be able to trace someone else's version and predict exactly what it returns.

Linear search is also one of the clearest examples of a pattern that runs through the whole course: traverse a collection and act on each element. Once you understand it, you've basically understood the skeleton behind finding a max, counting matches, or checking whether any element meets a condition. That's why it shows up so often in code-tracing questions and as a building block inside larger free-response methods.

How Linear Search Algorithm connects across the course

Iteration and for loops (Unit 2)

A linear search is really just a for loop with an if statement inside it. The loop handles the "check each element in order" part. The early return handles "stop once you find it." If you can trace a loop's control variable step by step, you can trace any linear search.

Array and ArrayList traversal (Unit 4)

The algorithm is identical for both structures. Only the syntax changes. Arrays use arr.length and arr[i], while ArrayLists use list.size() and list.get(i). Exam questions love to swap one for the other, so keep both versions in your head.

2D array traversal (Unit 4)

Searching a 2D array is a linear search run once per row. The outer loop picks a row and the inner loop scans across it. That's exactly the row-by-row approach EK 4.14.A.2 describes.

Binary search (Unit 4)

Binary search is the faster sibling. It repeatedly cuts a sorted list in half instead of checking every element. The tradeoff is that linear search works on any collection, sorted or not, while binary search only works if the data is already sorted.

Is Linear Search Algorithm on the AP® Computer Science A exam?

On the AP CSA exam, linear search mostly shows up in code-tracing multiple-choice questions. A typical stem gives you a method like findValue(int[] arr, int target) that loops from i = 0 to arr.length - 1, returns i when arr[i] == target, and returns -1 after the loop. Then it asks what a specific call returns. Your job is to step through the loop and stop at the first match. If the target isn't there, the answer is -1. Watch for duplicates, because a forward search returns the first occurrence and a backward search returns the last one.

You'll also see the same logic written for an ArrayList using list.size() and list.get(i), plus scenario questions. One example describes checking a 500-record ArrayList of student IDs one by one from index 0 and asks you to identify the algorithm or reason about how many comparisons it might take. In the worst case, it takes all 500.

No released FRQ has used the term "linear search" verbatim. Still, the pattern behind it (loop through a collection, check a condition, return or record a result) is the backbone of many array, ArrayList, and 2D array free-response methods. Common bugs the exam tests include putting return -1 inside the loop as an else (which quits after checking only one element), off-by-one loop bounds, and using == instead of .equals() to compare objects like Strings.

Linear Search Algorithm vs Binary Search

Both find a target value in a collection, but they work very differently. A linear search checks elements one by one from one end, so it works on unsorted data and can take as many comparisons as there are elements. A binary search requires sorted data. It checks the middle element and throws away half of the remaining elements each step, which makes it much faster on large collections. Quick test: if the code looks at index 0, 1, 2, 3... in order, it's linear. If it computes a middle index and moves a low or high bound, it's binary.

Key things to remember about Linear Search Algorithm

• A linear search checks each element of an array or ArrayList in order until it finds the target value or has checked every element.

• Linear search can start from either end of the collection, so a loop running backward from the last index is still a linear search.

• The standard Java version returns the index of the first match it finds and returns -1 if the target is not in the collection.

• To search a 2D array, you access each row and run a linear search across it, which means using a nested loop.

• Linear search works on unsorted data, but in the worst case it has to check every single element.

• A common bug is placing return -1 inside the loop, which ends the search after checking only the first element.

Frequently asked questions about Linear Search Algorithm

What is a linear search algorithm in AP Computer Science A?

It's a standard algorithm from Topic 4.14 that checks each element of an array or ArrayList in order until it finds the target value or reaches the end. It usually returns the index of the match, or -1 if the target isn't found.

Does a linear search have to start at index 0?

No. The CED (EK 4.14.A.1) says a linear search can begin from either end. Just remember that searching backward returns the last occurrence of a duplicate value instead of the first.

Does the array need to be sorted for a linear search?

No. That's the big advantage of linear search. It works on any collection in any order, while binary search only works on sorted data.

How is linear search different from binary search?

Linear search checks elements one at a time and works on unsorted data. Binary search needs sorted data and cuts the search space in half each step. In a 500-element list, a linear search might need up to 500 comparisons, while a binary search needs far fewer.

How do you do a linear search on a 2D array in Java?

Use an outer loop to access each row, then an inner loop to check each element in that row, returning as soon as you find the target. This row-by-row approach is exactly what EK 4.14.A.2 describes.