Inserting an Element into a Sorted Array
This example demonstrates how to determine the index at which an
element should be inserted into a sorted array. Although
binarySearch() is used to locate existent elements, it can also
be used to determine the insert index for non-existent elements.
Specifically, the insertion index is computed in the following way:
insert-index = (-return-value)-1
// Create anarray with an ordered list of items
String[] sortedArray = new String[]{"ant", "bat", "cat", "dog"};
// Search for a non-existent item and then insert it
int index = Arrays.binarySearch(sortedArray, "cow");
if (index < 0) {
// Compute the insert index
int insertIndex = -index-1;
// Insert the new item into sortedArray. The example here creates
// a new larger array to hold the new item.
String[] newSortedArray = new String[sortedArray.length+1];
System.arraycopy(sortedArray, 0, newSortedArray, 0, insertIndex);
System.arraycopy(sortedArray, insertIndex,
newSortedArray, insertIndex+1,
sortedArray.length-insertIndex);
newSortedArray[insertIndex] = "cow";
sortedArray = newSortedArray;
}
Post a comment