The Arrays Utility Class

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Utility class

A class that only holds static helper methods and is never instantiated, such as Arrays or Math.

In place

Changing the array you passed in, rather than returning a new one. Arrays.sort sorts in place.

Binary search

Finding a value in a sorted array by checking the middle and discarding the half that can't contain it, again and again.

Insertion point

The index where a missing key would go to keep the array sorted. binarySearch encodes it in its negative result.

Stable sort

A sort that keeps equal elements in their original order. Arrays.sort on objects is stable; on primitives stability doesn't matter.

Comparator

An object that decides the order of two values, used to sort in a custom way (Topic 9.10).

Fixed-size list

A list whose elements can be replaced but not added or removed. Arrays.asList returns one.

Lexicographic order

Dictionary order: compare first elements, and only if equal look at the next ones.

1. 1

   Decode binarySearch results

   On the sorted array [3, 7, 19, 25, 42], predict the result of searching for 1, 30 and 50 before running. (Insertion points 0, 4 and 5 give -1, -5 and -6.)

2. 2

   Sort a copy, keep the original

   Modify "Print, sort and search" so it prints both the original order and the sorted order at the end. You'll need nums.clone() or Arrays.copyOf before sorting.

3. 3

   Use fill for a memo table

   In the memoised Fibonacci of Topic 3.7, memo[n] != 0 was used to mean "computed". Rewrite it with Arrays.fill(memo, -1) and memo[n] != -1. Why is that more robust? (A legitimately computed 0 would no longer be mistaken for "not computed".)

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3);
        list.add(4);
    }
}

int[] u = {5, 1, 4, 2, 3};
System.out.println(Arrays.binarySearch(u, 1));
System.out.println(Arrays.binarySearch(u, 4));

1. 1

   Arrays lives in java.util, so add import java.util.Arrays;. Every method is static: you call it on the class, Arrays.sort(nums), passing the array as an argument. You never create an Arrays object.

2. 2

   Viewing and comparing: toString(a) gives [3, 7, 19]; deepToString does the same for nested arrays. equals(a, b) compares contents (and deepEquals for nested arrays). hashCode(a) gives a content-based hash.

3. 3

   Sorting and searching: sort(a) sorts in place in ascending order (a range version sorts part of the array). binarySearch(a, key) finds a key in a sorted array in O(log n) steps; if the key is missing it returns a negative number that encodes where it would go.

4. 4

   Filling and copying: fill(a, v) sets every element; copyOf(a, newLength) copies and pads or truncates; copyOfRange(a, from, to) copies a slice (to excluded). setAll(a, i -> ...) (Java 8) computes each element from its index.

5. 5

   Bridges to other APIs: asList(...) wraps an object array as a fixed-size List that writes through to the array; stream(a) (Java 8) opens a stream for sums, filters and more (Topic 10.4). Java 9 added mismatch (first differing index) and compare (dictionary order of two arrays).

6. 6

   Each method is overloaded for every primitive type and for objects, which is why you can call Arrays.sort on an int[], a double[] or a String[]. Sorting objects uses their natural order (Comparable) or a Comparator you pass in (Topic 9.10).

• ↔

  Arrays methods are tested, optimised and short, but they work on fixed-size arrays. Once you need to add and remove elements, move to collections (Phase 9), which offer similar helpers in Collections and List.

• ↔

  Sorting once (O(n log n)) and then binary searching many times (O(log n) each) beats repeated linear searches, but if you only search once, a single linear scan (O(n)) is cheaper than sorting.

• ↔

  Arrays.asList is a cheap view with no copying, but its fixed size and write-through behaviour surprise people. Copy when you need independence.

• Done when you can print, compare, fill and copy arrays with Arrays instead of loops.

• Done when you can sort whole arrays and ranges, and sort strings case-insensitively.

• Done when you can decode a negative binarySearch result into an insertion point.

• Done when you can explain why Arrays.asList lists can't grow and how to get one that can.

• Done when you know which sort algorithm is used for primitives vs objects and why.