JavaScript 如何高效地将数字插入到已排序的数字数组中

给定一组数字和任务是使用JavaScript将数字插入到已排序数组中。解决此问题有多种方法，其中两种如下：

方法1

首先，将值放入变量中（让我们称之为arr）。
确保它已排序。
在此示例中，复杂度为O(n)，其中n是数组中可用元素的数量。
方法 findLoc 正在搜索大于我们想要插入的元素的元素。
该方法返回位置的索引。
使用 .splice()方法 执行插入操作。

示例： 此示例说明了上述方法。

<h1 style="color:green;"> 
    GeeksforGeeks 
</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>

输出：

JavaScript 如何高效地将数字插入到已排序的数字数组中

方法2

在这个示例中，复杂度是O(Logn)，其中n是数组中的元素数量。
一个名为 findLoc 的方法正在寻找元素应该存在的位置。
该方法通过使用 二分搜索 算法返回位置的索引。
使用 .splice() 方法 执行插入操作。

示例： 这个示例演示了上面讨论的方法。

<h1 style="color:green;"> 
    GeeksforGeeks 
</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>

输出:

JavaScript 如何高效地将数字插入到已排序的数字数组中