Given an array of numbers and the task is to insert a number into the sorted array using JavaScript. There are many approaches to solving this problem two of which are given below:
Approach 1:
- First, take the values in a variable (lets arr).
- Make sure it is sorted.
- In this example, the complexity is O(n), where n is the number of elements in the array available.
- The method findLoc is searching for the element just greater than the element that we want to insert.
- The method returns the index of the location.
- perform the insert operation using the .splice() method.
Example: This example illustrates the approach discussed above.
html
<h1 style="color:green;"> neveropen </h1> <p id="GFG_UP"> </p> <button onclick="gfg_Run()"> Insert </button> <p id="GFG_DOWN"> </p> <script> var el_up = document.getElementById("GFG_UP"); var el_down = document.getElementById("GFG_DOWN"); var today = new Date(); var arr = [1, 2, 4, 6, 9]; el_up.innerHTML = "Click on the button to insert a number "+ "in javascript array.<br> Array is = " + arr; function add(el, arr) { arr.splice(findLoc(el, arr) + 1, 0, el); return arr; } function findLoc(el, arr, st, en) { st = st || 0; en = en || arr.length; for (i = 0; i < arr.length; i++) { if (arr[i] > el) return i - 1; } return en; } function gfg_Run() { add(7, arr); el_down.innerHTML = "Array becomes " + arr; } </script> |
Output:
What is the Efficient way to insert a number into a sorted array of numbers in JavaScript?
Approach 2:
- In this example, the complexity is O(Logn), where n is the number of elements in the array.
- A method findLoc is searching for the location where the element should be present.
- Method returns the index of the location by using binary search algorithm.
- perform the insert operation using .splice() method.
Example: This example illustrate the approach discussed above.
html
<h1 style="color:green;"> neveropen </h1> <p id="GFG_UP"></p> <button onclick="gfg_Run()"> Insert </button> <p id="GFG_DOWN"></p> <script> var el_up = document.getElementById("GFG_UP"); var el_down = document.getElementById("GFG_DOWN"); var today = new Date(); var arr = [1, 2, 4, 6, 9]; el_up.innerHTML = "Click on the button to insert a "+ "number in javascript array.<br> Array is = " + arr; function add(el, arr) { arr.splice(findLoc(el, arr) + 1, 0, el); return arr; } function findLoc(el, arr, st, en) { st = st || 0; en = en || arr.length; var pivot = parseInt(st + (en - st) / 2, 10); if (en - st <= 1 || arr[pivot] === el) return pivot; if (arr[pivot] < el) { return findLoc(el, arr, pivot, en); } else { return findLoc(el, arr, st, pivot); } } function gfg_Run() { add(5, arr); el_down.innerHTML = "Array becomes " + arr; } </script> |
Output:
What is the Efficient way to insert a number into a sorted array of numbers in JavaScript?
