Removing

To remove a value, we find it and then close the gap it leaves behind. That is the same find-then-shift pattern we used in the dynamic-array chapter. The only difference is that finding is now a binary search instead of a linear scan. The shift is similar to the one used in adding, but it goes left rather than right, because we are removing an element instead of making room for one.

public boolean remove(T value) {
  int i = indexOf(value);  // binary search
  if (i == -1) {
    return false;  // not here
  }
  for (int j = i; j < size - 1; j++) {
    arr[j] = arr[j + 1];  // shift the rest one slot left
  }
  size--;
  arr[size] = null;  // clear the vacated slot
  return true;
}

Take remove(7) from [1, 4, 7, 9]. First, indexOf(7) runs a binary search and finds 7 at index 2 (the index i marks it):

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

Now close the gap by sliding the rest one slot left. The 9 at index 3 copies into index 2, leaving a stale duplicate 9 at the end:

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

Finally, drop the size to 3 and clear that vacated last slot:

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

The remaining elements [1, 4, 9] are still in order. Every remaining element stays on the same side of every other remaining element that it was on before. Sorted order is only about relative position, so if the relative positions do not change, a sorted array stays sorted. So remove preserves the invariant no matter which element we take out.