Algorithms: Searching, Sorting, and Recursive Methods

Searching Algorithms

Searching is the fundamental process of finding a specific target element within a data structure. In AP Computer Science A, you are tested on two specific searching algorithms: Linear Search and Binary Search.

Linear Search (Sequential Search)

Linear search is the simplest searching algorithm. It checks every element in a list sequentially until the target is found or the end of the list is reached.

• Pre-condition: None (The data does not need to be sorted).
• Best Case: The target is at the first index ($1$ comparison).
• Worst Case: The target is at the last index or not present ($N$ comparisons).

/**
 * Returns the index of target in arr, or -1 if not found.
 */
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Target found
        }
    }
    return -1; // Target not found
}

Binary Search

Binary search is a much faster algorithm that uses a "divide and conquer" approach. It repeatedly divides the search interval in half.

• Pre-condition: The array or list MUST be sorted. If the data is unsorted, Binary Search will not work reliably.
• Mechanism: Compare the target to the element in the middle.
  • If equal, you are done.
  • If the target is smaller, search the left half.
  • If the target is larger, search the right half.

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        // Calculate mid index
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Target found
        } else if (target < arr[mid]) {
            right = mid - 1; // Discard right half
        } else {
            left = mid + 1;  // Discard left half
        }
    }
    return -1; // Target not found
}

Comparison: Linear vs. Binary

Iterative Sorting Algorithms

Sorting arranges data in a specific order (ascending or descending). You must be able to trace Selection Sort and Insertion Sort line-by-line.

Selection Sort

Selection Sort focuses on finding the extreme value (e.g., the minimum) and moving it to its correct place.

The Algorithm:

1. Scan the array from index $i$ to the end to find the index of the smallest element.
2. Swap that element with the element at index $i$.
3. Increment $i$ and repeat.

• Key Behavior: After pass $k$, the first $k$ elements are sorted and are the $k$ smallest elements in the list.

public static void selectionSort(int[] elements) {
    for (int i = 0; i < elements.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < elements.length; j++) {
            if (elements[j] < elements[minIndex]) {
                minIndex = j;
            }
        }
        // Swap elements[i] and elements[minIndex]
        int temp = elements[i];
        elements[i] = elements[minIndex];
        elements[minIndex] = temp;
    }
}

Insertion Sort

Insertion Sort works like organizing a hand of playing cards. You take a new card and slide it into the correct position among the cards you have already sorted.

The Algorithm:

1. Start at index 1 (assume index 0 is a "sorted" sub-list of length 1).
2. Take the value at current index ($temp$).
3. Shift items to the left of the current index to the right until you find the spot where $temp$ belongs.
4. Insert $temp$.

• Key Behavior: After pass $k$, the first $k+1$ elements are sorted relative to each other, but they are not necessarily the smallest elements of the entire original list.

Memory Aid: Selection vs. Insertion

• Selection: "Search and Swap." You search for the absolute minimum and swap it into place.
• Insertion: "Shift and Slide." You pick the next item and slide previous items over to make room.

Recursion

Recursion occurs when a method calls itself to solve a smaller version of the same problem. To solve a recursion problem on the AP exam, you must identify two components:

1. The Base Case: The condition where the recursion stops (returns a value without calling itself). Without this, you get infinite recursion (StackOverflowError).
2. The Recursive Step: The logic that calls the method again with values closer to the base case.

Analyzing Recursive Code (Tracing)

On the AP Exam, you will rarely write recursion from scratch but will frequently trace it.

Example: Factorial
n! = n \times (n-1)!

public int factorial(int n) {
    if (n == 1) return 1;        // Base Case
    return n * factorial(n - 1); // Recursive Step
}

The Call Stack

When a recursive call is made, the current method pauses using a Stack. The new call is placed on top. When the base case is hit, the stack "unwinds," passing values back down.

Recursive Searching and Sorting

Merge Sort

Merge Sort is a recursive sorting algorithm that uses the Divide and Conquer strategy. It is significantly faster than Selection or Insertion sort for large datasets.

The Algorithm:

1. Divide: Split the list into two roughly equal halves.
2. Conquer: Recursively sort each half (keep splitting until lists are size 0 or 1).
3. Merge: Combine the two sorted halves into a single sorted list.

Key Exam Facts for Merge Sort:

• It requires a temporary array (helper array) to merge elements, so it uses more memory.
• It is faster ($O(N \log N)$) than Selection/Insertion ($O(N^2)$).
• You do not need to memorize the code, but you must know how the merge step works (comparing the front of two lists and picking the smaller one).

Recursive Binary Search

Binary search can also be written recursively. The logic remains the same, but instead of a while loop, the method calls itself with updated low and high bounds.

public int recursiveBinarySearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1; // Base case: not found

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) return mid; // Base case: found
    else if (target < arr[mid]) 
        return recursiveBinarySearch(arr, target, low, mid - 1);
    else 
        return recursiveBinarySearch(arr, target, mid + 1, high);
}

Common Mistakes & Pitfalls

1. Binary Search on Unsorted Data:

   • Mistake: Trying to trace Binary Search on a list like [5, 2, 9, 1, 6].
   • Fix: Always check if the precondition "Sorted" is met. If strictly asked to trace it on unsorted data, follow the logic blindly, but usually, this is a trick question indicating the result is undefined or the element won't be found.

2. Off-by-One Errors in Binary Search:

   • Mistake: Updating boundaries to low = mid or high = mid.
   • Fix: You have already checked mid. You must move past it. Use low = mid + 1 and high = mid - 1.

3. Confusing Selection vs. Insertion Sort Traces:

   • Mistake: Thinking the array is partially sorted because the first few numbers are in order.
   • Fix: Look at the unsorted part. Selection Sort swaps (so the rest of the array might look messy but the beginning is strictly smallest). Insertion Sort shifts (so the beginning is sorted relative to itself, but smaller numbers might still exist deep in the array).

4. Infinite Recursion:

   • Mistake: Forgetting to move toward the base case (e.g., calling factorial(n) inside itself instead of factorial(n-1)).
   • Fix: Verify that every recursive call changes the parameters to eventually satisfy the base case condition.