Searching

Searching is the process of finding the index of a target value in an array or list. AP CSA tests two algorithms with very different requirements and performance characteristics.

Sequential search (also called linear search) walks the elements one at a time. It works on any data — sorted or not — but checks every element in the worst case.

Binary search repeatedly halves the search space. It is dramatically faster, but it only works on data that is already sorted.

On the AP exam, expect tracing questions, "how many comparisons?" questions, and FRQs that use search as a sub-step.

Sequential (linear) search

public static int sequentialSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

The standard "return -1 when not found" contract is universal across AP CSA. It signals failure clearly without using exceptions.

For Strings or other objects, use .equals() instead of ==.

Binary search

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Each iteration eliminates half the remaining elements. The array must be sorted for the algorithm to be valid — otherwise the comparisons lead in the wrong direction.

Comparing performance

• Sequential search: up to n comparisons for an array of n elements.
• Binary search: about log₂ n comparisons.

For 1,000 elements, sequential may need up to 1,000 checks; binary needs at most about 10.

When to use which

• Unsorted data → sequential search.
• Sorted data → binary search.
• Cost of sorting first usually doesn't pay off for one-time small searches.