1. Introduction
Manipulating sorted arrays is a common requirement in Java applications that maintain ordered collections either for efficient retrieval or ranking. In this example, I will show two methods to insert a number into a sorted array with the following steps:
- Find the insertion point via binary search. The binary search algorithm has
O(log n)time complexity. - Insert the element at the insertion position. It has
O(n)time and space complexity
2. Setup
In this step, I will create a simple Java project in Eclipse IDE with the Junit 5 library.
3. Array Sorted Insert Number Class
In this step, I will create a DemoInsertArray.java class with two methods: insert_via_Array and insert_via_List. Both methods have the same arguments: final int[] sortedArray, final int newNumber. The insert_via_List method uses sortedList.add(insertIdx, newNumber) to add the new number at the desired position while insert_via_Array method populates the new array with the following steps:
- Copy the original sorted array from the beginning to the insertion point to the new array.
- Add the new element at the found insertion position.
- Copy the remaining elements from the original array into the new array right after the added number.
DemoInsertArray.java
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | package org.jcg.zheng;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class DemoInsertArray { public int[] insert_via_Array(final int[] sortedArray, final int newNumber) { int insertIdx = Arrays.binarySearch(sortedArray, newNumber); if (insertIdx < 0) { insertIdx = -(insertIdx + 1); } int existingArrayLength = sortedArray.length; // create a new array with bigger size int[] newArray = new int[existingArrayLength + 1]; System.arraycopy(sortedArray, 0, newArray, 0, insertIdx); newArray[insertIdx] = newNumber; System.arraycopy(sortedArray, insertIdx, newArray, insertIdx + 1, existingArrayLength - insertIdx); return newArray; } public int[] insert_via_List(final int[] sortedArray, final int newNumber) { List<Integer> sortedList = new ArrayList<>(); for (int n : sortedArray) { sortedList.add(n); } int insertIdx = Collections.binarySearch(sortedList, newNumber); if (insertIdx < 0) { insertIdx = -(insertIdx + 1); } sortedList.add(insertIdx, newNumber); return sortedList.stream().mapToInt(n -> n).toArray(); }} |
- Line 11: use
Arrays.binarySearchto find the insertion position. The time complexity isO(log n). - Line 18: create a new Array. The space complexity is
O(n). - Line 20: use
System.arraycopyto copy the original array from the beginning to the insertion position. - Line 22: set the
newNumberat the inserting position of the new array. - Line 24: use
System.arraycopyto copy the original array after the insertion position to the new array. - Line 30, 35, 39, 41: similar to the
insert_via_Arraymethod, but it finds the insertion position viaCollections.binarySearchand adds the new number viasortedList.add(insertIdx, newNumber). It is easier as no manual shifting is needed.
3.2. Test Array Sorted Insert Number
In this step, I will create a DemoInsertArrayTest.java test class to test both methods defined in step 3. Figure 2 shows that the insert_via_Array method is faster than the insert_via_List method.
DemoInsertArrayTest.java
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | package org.jcg.zheng;import static org.junit.jupiter.api.Assertions.assertEquals;import java.util.stream.IntStream;import org.junit.jupiter.api.Test;class DemoInsertArrayTest { private DemoInsertArray testClass = new DemoInsertArray(); private int[] sortedArray = IntStream.range(1, 1000).toArray(); private int newNumber = 666; @Test void test_insert_via_Array() { assertEquals(999, sortedArray.length); assertEquals(667, sortedArray[666]); int[] updatedSortedArray = testClass.insert_via_Array(sortedArray, newNumber); assertEquals(1000, updatedSortedArray.length); assertEquals(666, updatedSortedArray[666]); } @Test void test_insert_via_List() { assertEquals(999, sortedArray.length); assertEquals(667, sortedArray[666]); int[] updatedSortedArray = testClass.insert_via_List(sortedArray, newNumber); assertEquals(1000, updatedSortedArray.length); assertEquals(666, updatedSortedArray[666]); }} |
- Line 18, 19, 28, 29: the sorted array length and 666 position value before the insertion.
- Line 22, 23, 32, 32: the sorted array length and 666 position value after the insertion.
Execute the Junit tests and capture the testing results:
As Figure 2 shows, test_insert_via_Array took 0.000 seconds which is faster than the test_insert_via_List‘s 0.016 seconds.
4. Conclusion
Inserting a number into a sorted array should be done efficiently for applications that maintain an ordered collection. Here are two application examples:
- A ranked leaderboard that shows the leader based on the score.
- A priority scheduler that tasks are added constantly and then inserted into the ordered priority position.
In this example, I showed two methods to insert a number into a sorted array. Both use the binary search to find the insert position but the insert_via_Array method uses System.arraycopy while the insert_via_List method uses sortedList.add(insertIdx, newNumber) to populate the new sorted array.
5. Download
This was an example of a Java project which inserted a number into a sorted array.
You can download the full source code of this example here: Insert a Number Into a Sorted Array Example
