{"id":128547,"date":"2024-11-22T18:48:54","date_gmt":"2024-11-22T16:48:54","guid":{"rendered":"https:\/\/www.javacodegeeks.com\/?p=128547"},"modified":"2024-11-19T10:19:30","modified_gmt":"2024-11-19T08:19:30","slug":"insert-a-number-into-a-sorted-array-example","status":"publish","type":"post","link":"https:\/\/www.javacodegeeks.com\/insert-a-number-into-a-sorted-array-example.html","title":{"rendered":"Insert a Number Into a Sorted Array Example"},"content":{"rendered":"

1. Introduction<\/h2>\n

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:<\/p>\n

    \n
  1. Find the insertion point via binary search<\/a>. The binary search algorithm has O(log n)<\/code> time complexity<\/a>.<\/li>\n
  2. Insert the element at the insertion position. It has O(n)<\/code> time and space complexity<\/a><\/li>\n<\/ol>\n

    2. Setup<\/h2>\n

    In this step, I will create a simple Java project in Eclipse IDE with the Junit 5 library.<\/p>\n

    \n
    \"Sorted<\/a>
    Figure 1. Sorted Array Insert Number Project<\/figcaption><\/figure>\n<\/div>\n

    <\/a>3. Array Sorted Insert Number Class<\/h2>\n

    In this step, I will create a DemoInsertArray.java<\/code> class with two methods: insert_via_Array<\/code> and insert_via_List<\/code>. Both methods have the same arguments: final int[] sortedArray, final int newNumber<\/code>. The insert_via_List<\/code> method uses sortedList.add(insertIdx, newNumber)<\/code> to add the new number at the desired position while insert_via_Array<\/code> method populates the new array with the following steps:<\/p>\n

      \n
    1. Copy the original sorted array from the beginning to the insertion point to the new array.<\/li>\n
    2. Add the new element at the found insertion position.<\/li>\n
    3. Copy the remaining elements from the original array into the new array right after the added number.<\/li>\n<\/ol>\n

      DemoInsertArray.java<\/em><\/span><\/p>\n

      package org.jcg.zheng;\n\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.Collections;\nimport java.util.List;\n\npublic class DemoInsertArray {\n\n\tpublic int[] insert_via_Array(final int[] sortedArray, final int newNumber) {\n\t\tint insertIdx = Arrays.binarySearch(sortedArray, newNumber);\n\t\tif (insertIdx < 0) {\n\t\t\tinsertIdx = -(insertIdx + 1);\n\t\t}\n\n\t\tint existingArrayLength = sortedArray.length;\n\t\t\/\/ create a new array with bigger size\n\t\tint[] newArray = new int[existingArrayLength + 1];\n\n\t\tSystem.arraycopy(sortedArray, 0, newArray, 0, insertIdx);\n\n\t\tnewArray[insertIdx] = newNumber;\n\n\t\tSystem.arraycopy(sortedArray, insertIdx, newArray, insertIdx + 1, existingArrayLength - insertIdx);\n\n\t\treturn newArray;\n\t}\n\n\tpublic int[] insert_via_List(final int[] sortedArray, final int newNumber) {\n\t\tList<Integer> sortedList = new ArrayList<>();\n\t\tfor (int n : sortedArray) {\n\t\t\tsortedList.add(n);\n\t\t}\n\n\t\tint insertIdx = Collections.binarySearch(sortedList, newNumber);\n\t\tif (insertIdx < 0) {\n\t\t\tinsertIdx = -(insertIdx + 1);\n\t\t}\n\t\tsortedList.add(insertIdx, newNumber);\n\n\t\treturn sortedList.stream().mapToInt(n -> n).toArray();\n\t}\n\n}\n<\/pre>\n