Searching, Removing, and Why No set()

We are working with the same SortedArray<T extends Comparable<T>>:

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
}

Exercise

Implement indexOf(T value) and contains(T value). Make use of insertionPoint where appropriate.

public int indexOf(T value) {
  // TODO: implement this method
}

public boolean contains(T value) {
  // TODO: implement this method
}

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;
}

Why does indexOf check i < size before checking arr[i].equals(value)?

Because insertionPoint can return size when value is larger than every element in the array. That is a valid return value; it just means value belongs past the last occupied slot, so there is no element there yet. Reading arr[i] without checking the bound first would throw an exception.

Exercise

Implement remove(T value). It finds and removes value, closes the gap, and returns whether an element was removed. Make use of indexOf when appropriate.

public boolean remove(T value) {
  // TODO: implement this method
}

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(9) finds it at index 2.

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │  9 │ 13 │ 20 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑
             i

The shift runs left-to-right from j = 2: arr[2] = arr[3] copies 13 into index 2, giving [2, 4, 13, 13, 20].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │ 13 │ 13 │ 20 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑    ↑
            i,j  j+1

arr[3] = arr[4] copies 20 into index 3, giving [2, 4, 13, 20, 20].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │ 13 │ 20 │ 20 │  _ │
└────┴────┴────┴────┴────┴────┘
                  ↑    ↑
                  j   j+1

Then size drops to 4 and arr[4] is cleared, leaving [2, 4, 13, 20].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │ 13 │ 20 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
                       ↑
                     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, the value itself decides where it goes. The client does not get to choose. That is why set does not fit the contract. DynamicArray makes no ordering promise, so the same operation is harmless there.