Linear Search (4.13.A)

Linear search scans every element from left to right until the target is found or the list is exhausted. You already wrote this in Lesson 4.5 — same algorithm, same code.

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

Works on any array — sorted or unsorted. In the worst case, examines every element.

Binary Search (4.13.A)

Binary search only works on a sorted array. It checks the middle element, then eliminates half the remaining search range each step:

1. Set low = 0, high = arr.length - 1.
2. Compute mid = (low + high) / 2.
3. If arr[mid] == target, return mid.
4. If target < arr[mid], search left half: high = mid - 1.
5. If target > arr[mid], search right half: low = mid + 1.
6. Repeat until found or low > high (not found — return -1).

Selection Sort (4.13.B)

Selection sort builds the sorted portion from left to right. On each pass, it finds the minimum of the remaining unsorted portion and swaps it into the next position.

// Starting array: {5, 3, 8, 1, 4}
// Pass 1: min=1 (index 3), swap with index 0 → {1, 3, 8, 5, 4}
// Pass 2: min=3 (index 1), already in place → {1, 3, 8, 5, 4}
// Pass 3: min=4 (index 4), swap with index 2 → {1, 3, 4, 5, 8}
// Pass 4: min=5 (index 3), swap with index 3 → {1, 3, 4, 5, 8}
// Done

After each pass, one more element is in its final sorted position at the left end.

Insertion Sort (4.13.B)

Insertion sort grows a sorted region from left to right. On each step, it takes the next unsorted element and inserts it into the correct position within the already-sorted left portion — shifting elements right to make room.

// Starting array: {5, 3, 8, 1, 4}
// Step 1: take 3, insert before 5 → {3, 5, 8, 1, 4}
// Step 2: take 8, already in place → {3, 5, 8, 1, 4}
// Step 3: take 1, insert at front → {1, 3, 5, 8, 4}
// Step 4: take 4, insert between 3 and 5 → {1, 3, 4, 5, 8}
// Done

Summary

• Linear search: works on any array, checks elements one by one, returns index or -1.
• Binary search: requires sorted array, eliminates half the search range each step, much faster than linear for large arrays.
• Selection sort: finds the minimum of the unsorted portion and swaps it into place each pass.
• Insertion sort: takes the next element and inserts it into the correct position in the sorted portion.