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)
{
high = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
Modify this code so:
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. Java’s 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’.)
