What is the Efficient way to insert a number into a sorted array of numbers in JavaScript ?
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;"> Â Â Â Â zambiatek </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;"> Â Â Â Â zambiatek </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?
