我如何找到数组的位置，其中一个整数应该在Javascript中更有效地插入

How do I find the array position in which an integer should be inserted in Javascript more efficiently?

本文关键字：整数 一个 插入 有效地 Javascript 数组 何找 位置      更新时间：2023-09-26

我最近完成了这个编程挑战(在FreeCodeCamp上):

返回值(第二个参数)所在的最低索引一旦排序后插入数组(第一个参数)。的返回值应该是一个数字。

例如，getIndexToIns([1,2,3,4]， 1.5)应该返回1，因为它大于1(索引0)，但小于2(索引1)。

同样，getIndexToIns([20,3,5]， 19)应该返回2，因为一旦数组已经排序，它看起来像[3,5,20]和19小于20(索引2)且大于5(索引1)。

我的代码可以工作，但是看起来效率很低，而且可能不必要地冗长。我不仅要解决挑战，还要成为一名编写高质量代码的优秀程序员。本着这种精神，我希望这里的Javascript专家能给我一些例子，告诉我如何更有效地解决这个问题。

function getIndexToIns(arr, num) {
  var diff = 0;
  var minDiff = 0;
  var insPos = 0;
  function sortNumber(a,b) {
    return a - b;
  }
  arr.sort(sortNumber);
  for(var i = 0; i < arr.length; i++){
    diff = num - arr[i];
    if(i === 0 || (diff < minDiff && diff >= 0)){
      minDiff = diff;
      if(arr[i] == num){
        insPos = i;
      }
      else{
        insPos = i + 1; 
      }
    }
  }
  return insPos;
}

谢谢你的帮助!

如果我们的输入数组是排序的，让要搜索(和插入)的项是整数或偶数对象，这项工作最好由二进制搜索算法完成。给定输入数组排序，这些比indexOf或findIndex快得多。因此，假设输入数组已经排序，下面的二进制搜索函数将返回搜索项的索引，或者如果不存在，它将返回一个负整数，指定插入索引。因此，如果它返回-3，则搜索项缺失，为了不破坏排序，应该在索引3处插入搜索项。

PS如果将不存在的项放在索引0处，将返回-0(负零)。

Array.prototype.sortedFindIndex = function(val, cb = x => x) { // default callback for primitive arrays
  var            deli = this.length-1,                         // delta index
                 base = 0,                                     // base to add the delta index
           expectedAt = i => { while (this[i] !== void 0 && cb(this[i]) < val) ++i;
                               return -i};
  while (deli > 0 && cb(this[base + deli]) != val) {
    deli = ~~(deli/2);
    cb(this[base + deli]) < val && (base += deli);
  }
  return cb(this[base + deli]) === val ? base + deli : expectedAt(base + deli);
};
var arr = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"},{a:7,b:"alf"},{a:8,b:"alf"},{a:9,b:"alf"},{a:10,b:"alf"},{a:11,b:"alf"},{a:13,b:"alf"}],
    brr = [3,6,7,9,13,15,18,21,22,25,29,33,37,42,65],
    idx = arr.sortedFindIndex(12, o => o.a);
console.log(idx);
idx = brr.sortedFindIndex(27);
console.log(idx);

var arr=[1,2,3,4,5];
function getIndexToIns(num) {
  var diff = 0;
  var minDiff = 0;
  var insPos = 0;  
  arr.sort(sortNumber);
  var pos=-1;
  for(var i = 0; i < arr.length; i++){    
    if(arr[i]>=num){
        pos=i;
        break;
      }
    }
  if(pos>=0){
    alert('Index: ' + pos);
  }else{
    alert('Not Found. Perhaps: at ' + arr.length);
  }
}
  function sortNumber(a,b) {
    return a - b;
  }
<input type="text" id="num">
<button type="button" onclick=getIndexToIns(document.getElementById('num').value);>Find Pos</button>

要找到最低索引需要执行三个步骤:1)向现有数组中添加新元素;2)对新数组中的所有数字执行升序排序;3)找到搜索到的索引。如果新数组的所有元素都是数字(这对于https://www.freecodecamp.com上的挑战来说已经足够了)

function getIndexToIns(arr, num) {
  var newArr = arr;
  newArr.push(num);  //add a new element num to the end of the array
  function compareNumbers(a,b){
    return a - b;
  }
  var sorted = newArr.sort(compareNumbers); //sort the numbers in the array
  for (var i = 0; i < sorted.length; i++)
    {
      if (sorted[i] === num) //index of the element equal to num is the index you are looking for
        {
          return i; 
        }
    }
}
getIndexToIns([2, 20, 10], 19);
相关文章：