4.14 Searching Algorithms

TLDR

Linear search checks each element of an array or ArrayList one at a time until it finds the target value or runs out of elements to check. In AP Computer Science A, linear search is the search algorithm you write and trace inside Unit 4 collections, and it works on any data whether or not it is sorted. You can start a linear search from either end, and for a 2D array you apply linear search to each row.

Searching algorithms at this point in the course means linear search, which checks each element of an array or ArrayList until it finds the target, and it often shows up inside a larger array, ArrayList, or 2D array problem. Binary search comes later alongside recursion, so you don't need it here.

How Linear Search Works and What It Returns

• Linear search checks elements in order until the target is found or every element has been checked.
• A linear search can start from the front or the back of an array or ArrayList.
• A common convention is to return the index when the target is found and return -1 when it is not.
• For object elements, compare with .equals() instead of == so you compare contents, not references.
• To linear search a 2D array, visit each row and run a linear search across that row.
• If the target appears more than once, decide whether you want the first match, the last match, or a count.

Linear Search Basics

Linear search, sometimes called sequential search, walks through a collection one element at a time. At each position you compare the current element to the target. If they match, you found it. If you reach the end without a match, the target is not in the collection.

The big advantage is that linear search works on any array or ArrayList, sorted or not. You do not need to prepare the data in any way before searching.

The tradeoff is speed. In the worst case you check every element, so the number of comparisons grows with the size of the collection. For small collections this is not a problem, and on the exam linear search is exactly what you are expected to write and trace.

Linear Search on an ArrayList

</>Java
import java.util.ArrayList;

public class LinearSearchDemo {
    // Returns the index of the first occurrence, or -1 if not found
    public static int linearSearch(ArrayList<Integer> list, int target) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == target) {
                return i;   // found it, return position
            }
        }
        return -1;          // checked everything, not found
    }

    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        numbers.add(15);
        numbers.add(8);
        numbers.add(23);
        numbers.add(8);
        numbers.add(42);

        System.out.println("Numbers: " + numbers);
        System.out.println("Find 23: index " + linearSearch(numbers, 23));
        System.out.println("Find 8: index " + linearSearch(numbers, 8)); // first occurrence
    }
}

The return i inside the loop stops the search as soon as a match is found, so this method returns the index of the first occurrence. The return -1 after the loop signals "not found."

Searching for Objects with equals

When the elements are objects such as String, compare with .equals() instead of ==. The == operator compares whether two references point to the same object, while .equals() compares the actual contents.

</>Java
import java.util.ArrayList;

public class WordSearch {
    // Counts how many times target appears
    public static int countOccurrences(ArrayList<String> words, String target) {
        int count = 0;
        for (String word : words) {
            if (word.equals(target)) {
                count++;
            }
        }
        return count;
    }
}

This version uses an enhanced for loop and keeps a counter, which is handy when the target can appear more than once and you want the total.

Starting From Either End

A linear search does not have to start at index 0. You can start at the last index and move toward the front. This is useful when you want the last occurrence of a value instead of the first.

</>Java
// Returns the index of the LAST occurrence, or -1 if not found
public static int lastIndexOf(ArrayList<Integer> list, int target) {
    for (int i = list.size() - 1; i >= 0; i--) {
        if (list.get(i) == target) {
            return i;
        }
    }
    return -1;
}

The logic is identical; only the direction of the loop changes.

Linear Search on a 2D Array

To search a 2D array, traverse it one row at a time and run a linear search across each row. This usually means nested loops: the outer loop picks a row, and the inner loop checks each element in that row.

</>Java
// Returns true if target is found anywhere in the 2D array
public static boolean contains2D(int[][] grid, int target) {
    for (int row = 0; row < grid.length; row++) {
        for (int col = 0; col < grid[row].length; col++) {
            if (grid[row][col] == target) {
                return true;
            }
        }
    }
    return false;
}

This visits elements in row-major order, meaning it finishes one full row before moving to the next. You could also return the row and column where the value was found by storing those indices before returning.

Writing and Tracing Linear Search Loops

Free Response: When a free-response prompt asks you to find or count something in a collection, a linear search loop is often the core of your answer. Read the specification carefully to decide what to return: an index, a boolean, a count, or the element itself. Then return -1 or the agreed value when nothing matches.

For a method that searches an ArrayList and might remove matches, be careful with the loop counter so you do not skip elements after a removal.

Code Tracing: For multiple-choice questions, you often trace a search loop with a small sample collection. Track the loop index and the current element at each step, and watch for the exact moment the condition becomes true. The method usually stops and returns right then, so later elements never get checked.

Common Trap:

• Comparing objects with == instead of .equals() can make a search miss a match that is really there.
• Returning too early or too late: make sure return -1 is after the loop, not inside it, so you do not report "not found" before checking every element.

Common Misconceptions

• Misconception: Linear search requires sorted data.
  Actually: Linear search does not require sorted data. It works on any array or ArrayList in any order.
• Misconception: Returning -1 is a rule.
  Actually: Returning -1 is a convention, not a rule. A method could instead return a boolean or the element itself, depending on the specification.
• Misconception: A match always means index 0 onward.
  Actually: A match does not always mean index 0 onward. Linear search can start from the back, which is how you find a last occurrence.
• Misconception: == and .equals() are interchangeable for objects.
  Actually: == and .equals() are not interchangeable for objects. Use .equals() to compare contents when searching for objects like strings.
• Misconception: Searching a 2D array is one single loop.
  Actually: Searching a 2D array is not one single loop. You need to reach each row and then search across that row, usually with nested loops.
• Misconception: Finding one match is always the goal.
  Actually: Finding one match is not always the goal. If duplicates exist, you may need to keep scanning to count them or to find the last one.

Related AP Computer Science A Guides

• 4.4 Traversing Arrays
• 4.5 Developing Algorithms Using Arrays
• 4.1 Ethical and Social Implications
• 4.11 2D Arrays
• 4.13 Implementing 2D Array Algorithms
• 4.16 Recursion