Given the following binary search algorithm:

public int binarySearch(Comparable[] objArray, Comparable searchObj) { int low = 0; int high = objArray.length - 1; int mid = 0; while (low <= high) { mid = (low + high) / 2; if (objArray[mid].compareTo(searchObj) < 0) { low = mid + 1; } else if (objArray[mid].compareTo(searchObj) > 0) { high = mid - 1; } else { return mid; } } return -1; }

How would you modify this 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. 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.