Solution: Fields and Finding a Key

public class SortedArrayMap<K extends Comparable<K>, V> implements Map<K, V> {

  private K[] keys;    // kept in ascending order
  private V[] values;  // values[i] is the value for keys[i]
  private int size;    // how many pairs the map holds

  @SuppressWarnings("unchecked")
  public SortedArrayMap() {
    keys = (K[]) new Comparable[10];  // start with room for 10 pairs
    values = (V[]) new Object[10];
    size = 0;                         // the map starts empty
  }

  @Override
  public int size() {
    return size;
  }
}

The keys array is created as a Comparable[] and cast to K[]. This is the same idiom SortedArray uses: K is bounded by Comparable<K>, so its erasure is Comparable, not Object. The values array has no bound, so it is an Object[], as in ArrayList.

Every operation starts by searching keys for a key. We write that search once and reuse it. SortedArray already has the search we need: insertionPoint. It runs binary search and returns the key’s index if the key is present, and otherwise the index where the key belongs. The version here is the same method with keys in place of arr, so I will not repeat it.

put needs the insertion point itself, because a new key goes there. get, containsKey, and remove only need to know whether the key is present and where. For those, a second helper turns the insertion point into an index, or -1 when the key is absent:

private int indexOf(K key) {
  int i = insertionPoint(key);
  if (i < size && keys[i].equals(key)) {
    return i;
  }
  return -1;
}

The i < size check comes first, because the insertion point can be size when the key is larger than every key in the map. There is no key at that index to compare against.

@Override
public V get(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  int i = indexOf(key);
  if (i == -1) {
    return null;  // key not present
  }
  return values[i];
}

@Override
public boolean containsKey(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  return indexOf(key) != -1;
}

Both call indexOf, so each is $O(\log n)$. get reads the value at the same index where it found the key.