Unit 4 Cycle 1 Day 16: Linear Search
Share
Linear Search
Section 4.6 — Searching
Key Concept
Linear search examines each element sequentially until the target is found or the end of the collection is reached. It works on any array or list, sorted or unsorted. The worst case checks every element (O(n)). The AP exam tests linear search implementations and asks about the number of comparisons for specific inputs. A common variation returns the index of the found element or -1 if not found. Enhanced for loops can implement linear search for existence checks but not for index-returning versions.
Consider the following method.
What does search(new int[]{4, 8, 2, 7, 1}, 7) return?
Answer: (B) 3
Searching for 7: i=0(4), i=1(8), i=2(2), i=3(7 found!). Returns index 3.
Why Not the Others?
(A) The method returns the INDEX, not the value. 7 is found at index 3.
(C) Index 4 contains 1, not 7.
(D) -1 means not found. 7 IS in the array at index 3.
Common Mistake
Linear search returns the INDEX where the target is found, not the target value itself. -1 is the conventional return value for "not found."
AP Exam Tip
Linear search: O(n) time. Checks each element sequentially. Returns the first matching index. Works on unsorted arrays.