Searching and Sorting in AP CSA

The AP exam requires you to implement, trace, and analyze both linear and binary search, plus selection and insertion sort. Efficiency comparisons appear every year.

Linear Search

Check each element one by one. Works on any array. O(n) time.

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;    // found at index i
        }
    }
    return -1;           // not found
}

Binary Search

Requires a sorted array. Eliminates half the remaining elements each step. O(log n) time.

public static int binarySearch(int[] arr, int target) {
    int low = 0, 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;
}

Algorithm Comparison