Linear search (also called sequential search) is an algorithm that checks each element of an array or ArrayList in order, one at a time, until it finds the target value or reaches the end. It works on unsorted data and takes up to n comparisons in the worst case.
Linear search is the most straightforward way to find something in a list. You start at index 0, compare each element to the target, and stop the moment you find a match (usually returning the index) or fall off the end of the list (usually returning -1 or some other "not found" signal). That's the whole algorithm.
In AP CSA, you'll see it written as a simple for loop over an array or ArrayList, and sometimes recursively, where each call checks one element and passes the rest of the list to the next call. Its superpower is that it makes zero assumptions about the data. The list can be sorted, unsorted, full of duplicates, whatever. Its weakness is speed. In the worst case (target is last or missing), it makes n comparisons for a list of n elements, so doubling the list doubles the work.
Searching shows up alongside arrays and ArrayLists in the heart of the AP CSA course, and linear search is the baseline algorithm everything else gets compared to. When the exam asks you to reason about "number of statement executions" or to compare algorithm efficiency informally, linear search is the O(n) reference point. It's also your only legal option when the data isn't sorted, which is exactly the trap the exam loves. Binary search is faster, but it demands sorted data first. Understanding linear search well means you can trace a loop, count comparisons, handle the "element not found" case, and explain why a slower-but-always-correct algorithm sometimes beats a faster one with preconditions.
Keep studying AP Computer Science A Unit 4
Binary Search (Units 7 & 10)
Binary search is the natural foil. It cuts the search space in half each step (about log n comparisons) but only works on sorted data. Linear search is slower but works on anything. AP questions love asking which one is appropriate for a given situation.
Sorting Algorithms (Unit 7)
Sorting is the price of admission for binary search. If you'd only search a list once, a linear search is often cheaper than sorting first and then binary searching. That cost-benefit reasoning is exactly the kind of informal efficiency comparison the course expects.
Time Complexity (Units 7 & 10)
Linear search is the classic O(n) example. AP CSA doesn't use Big-O notation formally, but it does ask you to count statement executions, and a linear search over n elements gives you the cleanest case of "work grows in direct proportion to list size."
Merge Sort (Units 7 & 10)
Both linear search and merge sort have recursive versions on the exam, and both raise the same hidden question about the call stack. A recursive linear search makes one call per element, so its worst-case call-stack depth is O(n), much deeper than recursive binary search's O(log n).
Linear search shows up mostly in multiple choice. Typical stems give you a search loop and ask what it returns for a specific input, how many comparisons it makes in the best or worst case, or what happens when the target isn't in the list. A favorite comparison question contrasts it with binary search, including the trap where binary search runs on unsorted data and returns wrong answers while linear search would have worked fine. Practice questions also test the recursive version, especially its worst-case space complexity. Each recursive call adds a stack frame, so searching a list of n elements can stack up n calls, which is O(n) space. On FRQs, you won't be told "write a linear search" by name, but array and ArrayList methods like "return the index of the first occurrence" or "return true if the list contains a value" are linear searches in disguise, and you should be able to write one cold.
Linear search checks elements one by one from the front and works on any list, sorted or not, taking up to n comparisons. Binary search repeatedly checks the middle and discards half the list, taking about log n comparisons, but it only works correctly on sorted data. If you run binary search on an unsorted list, it can miss elements that are actually there. Linear search never has that problem. The exam tests this exact distinction, so remember the rule. Unsorted data means linear search; sorted data makes binary search worth it.
Linear search checks each element in order from index 0 until it finds the target or reaches the end, then typically returns the index or -1 if the value isn't found.
It requires no preconditions, so it works on unsorted lists, which binary search does not.
Worst case is n comparisons when the target is the last element or not in the list at all, and best case is 1 comparison when the target is first.
A recursive linear search has O(n) worst-case space complexity because each of the n calls adds a frame to the call stack.
On the AP exam, FRQ tasks like "find the index of the first occurrence" or "check whether the list contains a value" are linear searches you write yourself with a for loop.
If data will only be searched once, linear search can beat the combined cost of sorting the data and then running binary search.
Linear search (or sequential search) is an algorithm that checks each element of an array or ArrayList in order until it finds the target value or reaches the end. It's usually written as a for loop that returns the matching index, or -1 if the value isn't found.
No. Linear search checks every element in order and works on any list, while binary search jumps to the middle and halves the search space each step but only works on sorted data. Binary search is much faster (about log n vs. n comparisons), but it gives wrong results on unsorted lists.
No, and that's its biggest advantage. Linear search works correctly on completely unsorted data because it checks every element anyway. Binary search is the one that requires sorted data first.
The worst case is n comparisons for a list of n elements, which happens when the target is the very last element or isn't in the list at all. For the recursive version, the worst case also means O(n) space because of n stacked recursive calls.
Effectively yes, just not by name. Array and ArrayList FRQs regularly ask you to find a value, return its index, or check if it exists, and the expected solution is a linear search loop. You should be able to write one from scratch, including the not-found case.