简单（演示）：

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

就像单个数据点一样，为了测试，我使用 Windows 7 上的 Chrome 使用两种方法将 1000 个随机元素插入到 100,000 个预排序数字的数组中：

First Method:
~54 milliseconds
Second Method:
~57 seconds

所以，至少在这个设置上，本地方法并不能弥补它。即使对于小数据集也是如此，将 100 个元素插入到 1000 的数组中：

First Method:
1 milliseconds
Second Method:
34 milliseconds

非常好的问题，非常有趣的讨论！Array.sort()在包含数千个对象的数组中推送单个元素后，我也使用了该函数。

locationOf由于具有复杂的对象，因此我必须为我的目的扩展您的函数，因此需要像 in 的比较函数Array.sort()：

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

您的代码中存在错误。它应该是：

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

如果不进行此修复，代码将永远无法在数组的开头插入元素。

我知道这是一个已经有答案的老问题，还有许多其他不错的答案。我看到一些答案建议你可以通过在 O(log n) 中查找正确的插入索引来解决这个问题 - 你可以，但你不能在那个时候插入，因为数组需要被部分复制出来空间。

底线：如果你真的需要 O(log n) 插入和删除到一个排序的数组中，你需要一个不同的数据结构 - 而不是数组。您应该使用B-Tree。将 B 树用于大型数据集所带来的性能提升将使这里提供的任何改进相形见绌。

如果必须使用数组。我提供了以下基于插入排序的代码，当且仅当数组已经排序时，它才有效。这对于每次插入后都需要求助的情况很有用：

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

它应该在 O(n) 中运行，我认为这是你能做的最好的。如果js支持多重赋值会更好。 这是一个可以玩的例子：

更新：

这可能会更快：

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

更新 2

@terrymorse 在评论中指出 javascripts Array.splice 方法非常快，它不仅仅是时间复杂度的不断改进。似乎正在使用一些链表魔术。这意味着您仍然需要与普通数组不同的数据结构 - 只是 javascript 数组可能会提供不同的数据结构。

更新了 JS Bin 链接