The SortedArray

Binary search only works on sorted data. So far we have been assuming the array we hand it happens to be sorted. But nothing in the binarySearch method enforces that. If the client passes an unsorted array, the search will not work correctly. The client has to know to sort the array first, and to keep it sorted after that. That is a lot of responsibility for the client to take on.

Let’s build a structure that takes on this responsibility itself: the SortedArray. It is a list, much like DynamicArray, but it makes one extra promise to keep its elements in sorted order. That way, the client can always call binarySearch on it and be sure it will work correctly.

The invariant

A SortedArray guarantees that its elements are always in sorted order. No matter what the client does to it, reading it back from index 0 upward always gives a non-decreasing sequence.

Note the “at all times” part. It is not enough for the array to be sorted most of the time, or to be sorted once we finish a batch of work. Every method has to leave it sorted before it returns, because the next thing the client calls might be a binary search that depends on it.

Fields and constructor

A SortedArray is array-backed, exactly like DynamicArray:

public class SortedArray<T extends Comparable<T>> {
  private T[] arr;
  private int size;

  @SuppressWarnings("unchecked")
  public SortedArray() {
    arr = (T[]) new Comparable[10];
    size = 0;
  }

  // ... get, size, add, contains, remove ...
}

Two things to notice:

• The type parameter is bounded: <T extends Comparable<T>>. A SortedArray needs this because it must be able to compare elements to maintain the sorted order. Recall bounding T by Comparable<T> is what makes compareTo available to us, which we need to compare elements.
• The backing array is created with the same (T[]) new ... idiom we used for DynamicArray but with Comparable instead of Object when we allocate it. This is because T is bounded by Comparable. If we allocated an Object[] we would not be able to cast it to T[] because Object does not implement Comparable.

When the backing array fills up we grow it exactly as DynamicArray does, with a private grow() that allocates a larger array and copies the elements over.

get and size

Neither get nor size modifies anything, so neither one can break the invariant. We can implement them exactly as we did for DynamicArray:

public T get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  return arr[index];
}

public int size() {
  return size;
}

The operations that change the contents are the ones that need work, because each one has to leave the array sorted.