The first part of this assignment is to modify the binary search algorithm such that the following conditions are met:

1. The algorithm returns an index where a specified item should be inserted such that the ordering of all items will be preserved after the insertion has occurred. Note that we are not concerned here with performing the actual insertion, only with returning the insertion point.

2. The algorithm should always return a non-negative integer regardless of whether or not the item to be inserted is already in the array. Again, since we are not concerned with performing the actual insertion, it is acceptable for the algorithm to return an index that is greater than the current length of the array. It will be assumed that some other method will handle any array resizing and item shifting. In other words, assume someone else will be writing an insert method that is responsible for actually inserting items into an array. This method would call your modified binarySearch algorithm to get the correct insertion index, and then insert the item.

3. Your algorithm must use Comparable objects. Do not write the algorithm so that it only works with primitive data values such as int or double. If you want to use integers or primitive data, use the built-in wrapper classes (Integer, Double, Long, Float, Character, Byte, etc.). These wrapper classes already implement the Comparable interface, so they are Comparable objects. Javas autoboxing feature will automatically convert a primitive data value to the appropriate wrapper type, eliminating the hassle of manually instantiating wrapper objects. For example, you can create an array of Integer objects by typing: Integer[] intArray = {1, 2, 3, 4, 5, 6};. (One cautionary note: keep in mind that characters and character strings are compared using ASCII codes, which means, for example, that an upper case Z is considered to be less than a lower case a.)

4. I will test your code by pasting your modified method in my own test harness. Be sure to remove all debugging code from your method, and make sure your method does not need to call other methods or reference any global variables in order to work. Testing Your Implementation By now, Im sure everyone is aware of the importance of testing code, but because this particular assignment lends itself well to being an exercise in test case generationsince the test cases for this problem can be easily elucidatedwe will incorporate test case creation as part of the assignment. There are 3 conditions that need to be tested that are related to the positioning of the item being inserted: 1. the lower boundary of the array 2. the upper boundary of the array 3. between the upper and lower boundaries of the array

For each of the three conditions there are two possibilities: 1. the item already exists in the array 2. the item does not exist in the array

Furthermore, the array may contain: 1. an odd number of items, or 2. an even number of items.

The combinations of the above factors yield a total of 3 * 2 * 2, or 12 test categories, assuming the array is not empty. The empty array yields a 13th test category, which should also be tested. To test your code, do the following:

1. Create a set of 13 test cases, one test case for each of the 13 test categories described above. Recall that every test case should consist of 1) inputs and 2) expected output. Each test case should consist of an array of Comparable objects and an object of the same type to be inserted into the array, as inputs, and the correct insertion point for the item to be inserted, as the expected output. You can create your tests using jUnit or some other testing library, or you can create your own test harness. A test harness is simply a program that passes the inputs of test cases to the code to be tested, and checks the actual output against the expected output. The results are displayed on the screen or written to a testing log file.

2. With your test cases in hand, test your modified binarySearch method.