GROUNDWORK
Chapter 11 - Searching and Sorting

Name: ________________________________     Date: ______________

Fill in every blank. Where a term is asked for, write the word the course
uses. Where code is asked for, write exact Java. Where output is asked
for, write what the program prints, one line per line.


VOCABULARY
----------

 1. A __________________ is a procedure for solving a problem: a finite
    sequence of unambiguous steps that turns an input into the right
    output.

 2. Looking at each item in an array, one after another, until you find
    the target, is called __________________.

 3. Searching a sorted array by repeatedly checking the middle of the
    remaining range and throwing away half is called __________________.

 4. The standard notation for describing how an algorithm's work scales as
    the input grows, deliberately ignoring constant factors and machine
    speed, is called __________________.

 5. Selection sort and bubble sort both make roughly n squared comparisons
    in the worst case, which puts them in the __________________ class,
    notated O(n squared).


READING CODE
------------

 6. What does this print?

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

        void main() {
            int[] numbers = {17, 4, 23, 8, 42, 15, 9};
            IO.println(linearSearch(numbers, 42));
            IO.println(linearSearch(numbers, 99));
        }

    ____________________________________

 7. What does this print?

        int binarySearch(int[] items, int target) {
            int low = 0;
            int high = items.length - 1;

            while (low <= high) {
                int middle = (low + high) / 2;

                if (items[middle] == target) {
                    return middle;
                } else if (items[middle] < target) {
                    low = middle + 1;
                } else {
                    high = middle - 1;
                }
            }

            return -1;
        }

        void main() {
            int[] numbers = {4, 8, 9, 15, 17, 23, 42};
            IO.println(binarySearch(numbers, 42));
            IO.println(binarySearch(numbers, 4));
            IO.println(binarySearch(numbers, 99));
        }

    ____________________________________

 8. What does this print?

        int[] selectionSort(int[] items) {
            int[] result = Arrays.copyOf(items, items.length);

            for (int i = 0; i < result.length; i++) {
                int smallest = i;
                for (int j = i + 1; j < result.length; j++) {
                    if (result[j] < result[smallest]) {
                        smallest = j;
                    }
                }
                int temp = result[i];
                result[i] = result[smallest];
                result[smallest] = temp;
            }

            return result;
        }

        void main() {
            int[] numbers = {64, 25, 12, 22, 11};
            IO.println(Arrays.toString(selectionSort(numbers)));
        }

    ____________________________________

 9. What does this print?

        ArrayList<String> words = new ArrayList<>(
                List.of("Banana", "apple", "Cherry"));
        Collections.sort(words);
        IO.println(words);
        words.sort(Comparator.comparing(s -> s.toLowerCase()));
        IO.println(words);

    ____________________________________

10. What does this print?

        record SearchResult(int index, int comparisons) {}

        SearchResult linearSearchCounted(int[] items, int target) {
            int comparisons = 0;
            for (int i = 0; i < items.length; i++) {
                comparisons++;
                if (items[i] == target) {
                    return new SearchResult(i, comparisons);
                }
            }
            return new SearchResult(-1, comparisons);
        }

        void main() {
            int[] numbers = {5, 3, 8, 1, 9};
            SearchResult result = linearSearchCounted(numbers, 1);
            IO.println(result.index() + " " + result.comparisons());
        }

    ____________________________________


WRITING CODE
------------

11. Complete the loop bound so that every index in items gets checked:
    int linearSearch(int[] items, int target) {
        for (int i = 0; i < __________________; i++) {

12. Complete the line that finds the middle index. On two ints, this
    operator drops any fraction, so the middle is always a whole index:
    int middle = (low + high) __________________ 2;

13. Complete the swap that puts the smallest value found so far into
    position i:
    int temp = result[i];
    result[i] = __________________;
    result[smallest] = temp;


WHY IT WORKS
------------

14. Binary search only works correctly when the array is already
    __________________, because each step assumes everything below the
    middle is smaller and everything above is larger.

15. Linear search is described as O(n) because doubling the size of the
    array __________________ the number of comparisons needed in the worst
    case.

16. A HashMap lookup stays fast no matter how large the map grows, because
    it does not check keys one at a time the way linear search does - that
    is why a HashMap lookup is O(__________________), constant time
    regardless of size.