Question: The operations that are supported by the SortedSet can also be implemented by using an array and maintaining the current size. The array elements are stored in sorted order in consecutive array positions. Thus contains can be implemented by a binary search. Do the following:
a. Describe the algorithms for add and remove.
b. What is the running time for these algorithms?
c. Write an implementation that uses these algorithms, using the protocol in Figure.
d. Write an implementation that uses these algorithms, using the standard Sorted Set protocol.
1. package weiss.nonstandard;
2
3 // SimpleContainer protocol
4 public interface SimpleContainer
5 {
6 void insert( AnyType x);
7 void remove( AnyType x);
8 AnyType find( AnyType x);
9
10 boolen isEmpty( );
11 void makeEmpty( );
12 }