The Sorted Array Set

SortedArraySet implements the Set ADT (add, remove, contains, and size) with a backing array that is always kept in sorted order:

public class SortedArraySet<T extends Comparable<T>> implements Set<T> {

  private T[] arr;   // the backing array, kept in sorted order
  private int size;  // how many items the set holds

  // the operations go here
}

Solution

size is $O (1)$ : it returns a field. contains is $O (lo g n)$ : it is a binary search. add is $O (n)$ : binary search finds the insertion point in $O (lo g n)$ , but the items from the insertion point to the end shift one slot to the right to make room. remove is $O (n)$ : binary search finds the item in $O (lo g n)$ , but the items after it shift one slot to the left to close the gap.

Solution

The last item is the largest. Copying it into a gap in the middle would leave the array unsorted, and binary search would no longer work.

Solution

The unsorted implementations only need to tell whether two items are equal, and equals does that. To keep the array sorted and to run binary search, SortedArraySet also has to tell which of two items comes first. The bound guarantees that every item has a compareTo method.

Solution

$O (n)$ . Binary search has to reach the middle item of the range in $O (1)$ . An array does that with an index. A linked list can reach its middle node only by following the links from the head, which is $O (n)$ , so the search stays $O (n)$ .