Searching, Removing, and Why No set()

We are working with SortedArray<T extends Comparable<T>>, an array-backed list that keeps its elements in sorted order. grow() and add(T value) are already implemented, and so is a private insertionPoint(T value), which returns the index of value if it is present, or the index where it should be inserted otherwise.

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

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

  // grow(), insertionPoint() and add() are already implemented
}
Solution
public int indexOf(T value) {
  int i = insertionPoint(value);
  if (i < size && arr[i].equals(value)) {
    return i;
  }
  return -1;
}

public boolean contains(T value) {
  return indexOf(value) != -1;
}
Solution
public boolean remove(T value) {
  int i = indexOf(value);
  if (i == -1) {
    return false;
  }
  for (int j = i; j < size - 1; j++) {
    arr[j] = arr[j + 1];
  }
  size--;
  arr[size] = null;
  return true;
}
Solution

indexOf(33) finds it at index 2.

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 33 │ 42 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑
             i

The shift runs left-to-right from j = 2: arr[2] = arr[3] copies 42 into index 2, giving [11, 25, 42, 42, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 42 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑    ↑
            i,j  j+1

arr[3] = arr[4] copies 58 into index 3, giving [11, 25, 42, 58, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 58 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
                  ↑    ↑
                  j   j+1

Then size drops to 4 and arr[4] is cleared, leaving [11, 25, 42, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 58 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
                       ↑
                     size
Solution

set would let the client put any value at any index. An arbitrary index does not preserve sorted order. On [2, 4, 9, 13], set(1, 100) produces [2, 100, 9, 13], and that breaks the invariant. Every other method, including insertionPoint, assumes the array is sorted, so once the invariant breaks, those methods start returning wrong answers. In a SortedArray, an element’s position is fixed by its value, so the client cannot choose it.