In the current implementation of the RecordDB class, the insert and the delete methods don't take advantage of the fact that the array of records is in sorted order (by ssn). In fact, most of code for the search method could have been reused by the insert and delete methods. This homework asks you to modify the RecordDB class to do just this. Here are the specific modifications you should make.

1. Make a private method called binarySearch method that can be used by all three public methods, insert, search, and delete. Given a social security number s, the binarySearch method should behave as follows:
   • if the array contains a record with social security number s, then the index of this record should be returned,
   • otherwise, it should return an index i such that records in slots with index less than i have social security numbers smaller than s and records in slots with index i or more have social security numbers larger than s. In other words, if a record with social security number s were to be inserted into the array, it would go into slot i.
2. The above described binarySearch method can be used by insert, search, and delete quite easily. Modify these three methods to call the binarySearch method and use the result appropriately.

Call the updated RecordDB class, the optimizedRecordDB class. To comprehensively test this class, expand on the main method that is currently part of the RecordDB class. Make sure that all aspects of all of your methods get tested. For example, you should make sure that the insert method correctly inserts at the beginning of the array, at the end of the array, as well as somewhere in the middle of the array. Similarly, think about different cases that the other methods have to deal with, and make sure that your tests cover all of those cases.

Submit the following files: optimizedRecordDB.java, optimizedRecordDB.readme, and optimizedRecordDB.pdf. The last file should describe what cases you considered for each of your methods and how you tested these cases.