Using a Sorted Array to Implement a Set

The two heuristics improved the average search, but contains can still scan the whole structure in the worst case. Moving elements around one lookup at a time cannot fix that. To beat $O (n)$ , we have to arrange the elements so that a search can rule out many of them at once.

We already saw how to do this in the sorted-array chapter. When an array is kept in sorted order, binary search finds any element in $O (lo g n)$ , because each step halves the range it still has to consider. For the site with 1,000 accounts, that is about 10 comparisons for any login, compared with up to 1,000. SortedArraySet implements Set this way: it stores the elements in a backing array kept in sorted order.

To keep the array in order, the elements must be comparable to one another. The other implementations needed only equals, but this one also needs an ordering. We express that with the same type bound that SortedArray used:

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

  // ...
}

If the elements have no natural order, or we want a different one, the set could take a Comparator in its constructor instead. We will stay with Comparable here.

Operations and Complexity

size(): Return the stored size. $O (1)$ .

contains(item): Binary search. $O (lo g n)$ .

add(item): If binary search finds the item, return false. Otherwise insert it at its insertion point, with the same shift as SortedArray’s add: $O (n)$ .

remove(item): Binary search, then the same shift as SortedArray’s remove to close the gap: $O (n)$ . We cannot use ArraySet’s swap-with-last removal here. The last element is the largest, so moving it into the gap would leave the array unsorted.

Compared with the unsorted ArraySet, only contains got faster. add and remove are still $O (n)$ , but for a new reason. Their search now takes $O (lo g n)$ , and the $O (n)$ comes from shifting elements to keep the array sorted.

Sorted Linked List

Sorting would not help LinkedSet. Binary search needs to jump to the middle element in $O (1)$ . As we saw in the List ADT chapter, a linked list can reach its middle node only by following the links from the head, so binary search on it does not give $O (lo g n)$ .