Linear Search in AP Computer Science A

In AP Computer Science A, linear search is an algorithm that checks each element of an array, ArrayList, or String one at a time, in order, until it finds the target value or reaches the end. It works on unsorted data and can be written iteratively or recursively.

What is Linear Search?

Linear search is the "check every box" approach to finding something. You start at index 0, compare that element to your target, and move to the next index if it doesn't match. You keep going until you find a match (and usually return its index) or you run past the end of the collection (and usually return -1 to signal "not found").

The big thing linear search has going for it is that the data does not need to be sorted. It doesn't make any assumptions about order. It just looks at everything. That simplicity has a cost. In the worst case (the target is last or missing), it checks every single element. In AP CSA, linear search shows up as a regular loop traversal and also as a recursive method, where each call checks one index and then calls itself on the next index. Linear and binary search are the only two search algorithms in scope for the course and exam.

Why Linear Search matters in AP® Computer Science A

Linear search lives in Unit 4: Data Collections, under Topic 4.17 Recursive Searching and Sorting. It supports two learning objectives. Under 4.17.A (determine the result of executing recursive algorithms that use strings or collections), a recursive linear search is a textbook example of EK 4.17.A.1, which says recursion can be used to traverse String objects, arrays, and ArrayList objects. Under 4.17.B, linear search is the benchmark binary search gets measured against. EK 4.17.B.2 states that binary search is typically more efficient than linear search, and the exclusion statement confirms linear and binary are the only searches you need to know. Think of linear search as the "control group" for efficiency. You can't explain why binary search is faster until you understand what linear search does.

How Linear Search connects across the course

Binary Search (Unit 4)

Binary search is linear search's smarter, pickier sibling. Linear search works on any list but may check every element. Binary search only works on sorted data, but it throws away half the remaining elements with each check. That trade between flexibility and speed is exactly what EK 4.17.B.1 and 4.17.B.2 are getting at.

Traverse and Recursion (Unit 4)

A linear search is really just a traversal that stops early. Written recursively, each call handles one index and hands the rest of the list to the next call, with a base case for "ran off the end." That makes it one of the cleanest examples of EK 4.17.A.1, recursion traversing an array or ArrayList.

Time Complexity (Unit 4)

Linear search is your mental model for "work grows with the size of the list." Double the list, and the worst case doubles the number of comparisons. Binary search grows much more slowly, which is why it wins on large sorted collections.

Sorting Algorithms and Merge Sort (Unit 4)

Sorting and searching are linked. Binary search needs sorted data, so if your data is unsorted, you either sort it first (with something like merge sort) or just use linear search. For a one-time search on unsorted data, linear search is often the practical choice.

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

Linear search usually appears in multiple-choice questions in two ways.

1. Tracing recursive code. You may get a method like findString(ArrayList<String> list, String target, int index) that returns -1 when index >= list.size(), returns index when list.get(index).equals(target), and otherwise calls itself with index + 1. Your job is to recognize it as a recursive linear search and figure out what it returns or how many calls it makes. Watch the base case order and whether it uses .equals versus == for Strings.
2. Telling it apart from binary search. Many stems describe an algorithm ("checks the middle element," "eliminates half each iteration," "requires sorted data") and ask you to name it. If the description says it checks elements one by one from the start, it's linear. If it says middle and halves, it's binary.

No released FRQ has used the term verbatim. Still, FRQs constantly ask you to write loops that scan an array or ArrayList for a value that meets a condition, and that is a linear search in practice.

Linear Search vs Binary Search

Linear search checks elements one at a time from the start and works on unsorted data. Binary search starts at the middle of a sorted collection and eliminates half the remaining elements on each step (EK 4.17.B.1). Binary search is typically more efficient (EK 4.17.B.2), but it fails if the data isn't sorted. Quick test for a stem. If it says "middle" or "half," it's binary. If it says "each element in order," it's linear.

Key things to remember about Linear Search

• Linear search checks each element in order until it finds the target or reaches the end of the collection.

• Linear search does not require sorted data, which is its main advantage over binary search.

• In the worst case, linear search compares the target to every element, so its work grows directly with the size of the list.

• Linear search can be written with a loop or recursively, where each call checks one index and then calls itself on the next index.

• A typical linear search returns the index of the target if found and -1 if the target is not in the collection.

• Linear and binary search are the only search algorithms in scope for the AP Computer Science A exam.

Frequently asked questions about Linear Search

What is linear search in AP Computer Science A?

Linear search is an algorithm that checks each element of an array, ArrayList, or String one by one until it finds the target or reaches the end. It's covered in Topic 4.17 in Unit 4 and is the baseline that binary search gets compared against.

Does linear search need the array to be sorted?

No. Linear search works on unsorted data because it looks at every element in order without assuming anything about their arrangement. Binary search is the one that requires sorted data (EK 4.17.B.1).

Is linear search always slower than binary search?

No. The CED says binary search is typically more efficient (EK 4.17.B.2), not always. If the target is the first element, linear search finds it in one comparison. On small or unsorted lists, linear search can also be the more practical choice.

How is linear search different from binary search?

Linear search starts at index 0 and checks elements one at a time on any list. Binary search starts in the middle of a sorted list and cuts the search space in half each step. In a sorted array like [5, 12, 18, 25, 42, 58, 73, 91], binary search checks 25 first, while linear search would check 5 first.

Can linear search be written recursively on the AP exam?

Yes. A recursive linear search has a base case that returns -1 when the index passes the end of the list, returns the index on a match, and otherwise calls itself with index + 1. This is a direct example of EK 4.17.A.1, which says recursion can traverse arrays, ArrayLists, and Strings.