Efficient Way to Insert a Number Into a Sorted Array of Numbers in Java

1. Overview

The usage of arrays is very common in programming languages. Inserting and removing elements from an array of numbers is a basic operation we often need. Inserting an element into a sorted array of numbers is a special case of an array insertion.

Let’s see how to insert a number into a sorted array of numbers efficiently.

2. Introduction to Problem

To make inserting a number into a sorted array efficient, we need to minimize the number of position shifts and comparisons. We can achieve this by searching for the insertion index using binary search. Then, shift the elements to the right to make space for the new element.

For example, given that sortedArray is a sorted integer array:

int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };

We want to add a new element 90 to the array. The algorithm should insert the number after 85 and before 100 in an efficient manner:

int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };

3. Solution

The solution involves two steps. The first is to find the insertion index for the new number. The most efficient way of doing that is with a binary search. Once the index is found, we increase the size of the array by 1, shift the elements from the index up to the end to the right, and insert the new element at the calculated index:

public static int[] insertInSortedArray(int[] arr, int numToInsert) {
    int index = Arrays.binarySearch(arr, numToInsert);

    if (index < 0) {
        index = -(index + 1);
    }

    int[] newArray = new int[arr.length + 1];

    System.arraycopy(arr, 0, newArray, 0, index);

    newArray[index] = numToInsert;

    System.arraycopy(arr, index, newArray, index + 1, arr.length - index);

    return newArray;
}

Arrays.binarySearch(arr, element) returns the element insert index using binary search. The binarySearch() method returns a positive element insert index if the element is found in the array arr. If the element is not found in the array arr, it returns the negation of insert index plus one. Hence, if the returned index value is less than 0, we add 1 and negate it to get the insertion index.

We create a new array of size 1 more than that of the original array and insert the value at the calculated index in the new array. Then, to replicate the shifting of elements from the insert index to the end of the array, we copy values from the original array to the new array.

System.arraycopy() is used to efficiently copy the array before and after the insert index.

Let’s validate our code with a test case:

@Test
void givenSortedArray_whenElementInserted_thenArrayRemainsSorted() {
    int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };
    int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };
    int valueToInsert = 90;
    int[] resultArray = insertInSortedArray(sortedArray, valueToInsert);
    assertThat(expcetedArray).isEqualTo(resultArray);
}

The test case inserts new element 90 in the array sortedArray. Our insertion method insertInSortedArray() returns the result in the array resultArray. The test case matches the expected output array expectedArray with the result array resultArray. Since the test case passes successfully, it validates our array insertion logic.

Similarly, we can implement the solution for an array of numeric wrapper classes like Integer[], Double[], etc. The only change would be in array type, as both binarySearch() and arrayCopy() methods work with the wrapper class arrays.

4. Time Complexity

As discussed earlier, there are two steps in the solution. The binary search for calculating the insertion index has a time complexity of O(log n), and shifting of the elements has a complexity of O(n). Hence, the overall complexity of the solution is O(n).

5. Conclusion

In this article, we learned that a number can be inserted in a sorted array efficiently in Java by having two steps, i.e., binary search for figuring out the element insert index and right shifting of elements from the element insert index.