是否Arrays.binarySearch给我一个不包含的元素的正确位置？

Question

我想用最快的方式将新的元素到一个有序阵列和阵列必须插入后进行排序。所以，我有计划，我用System.arrayCopy，但有时我计算错误的间隔位置。

这里是我的代码：

int[] res; // filled with random numbers and sorted
int old; // the old value which I want to remove
int now; // the new value which I want to insert

int idx = Arrays.binarySearch(res, 0, res.length, old);
int idy = Arrays.binarySearch(res, 0, res.length, now);

if (0 > idy) { // the new value has not been in the array

    idy = -idy - 1;
}
if (res.length == idy) {

    idy -= 1;
}

if (idx < idy) {
    //                       old             now
    // --------------------- idx ----------- idy -----------
    System.arraycopy(res, idx + 1, res, idx, idy - idx);
} else if (idx > idy) {
    //                       now             old
    // --------------------- idy ----------- idx -----------
    System.arraycopy(res, idy, res, idy + 1, idx - idy);
}
res[idy] = now;

Arrays.binarySearch的Javadoc中表示：它返回搜索键的索引，如果包含在指定范围内的阵列中;否则，(-(insertion point) - 1)。如果在范围内的所有元素都小于指定的键中除密钥，或toIndex更大的范围中的第一个元素的索引：插入点被定义为将键插入到阵列的点。请注意，这保证了当且仅当此键被找到，返回值将是>= 0。

我插入随机整数[0..199]，RE的数组大小是666。

偶尔数组的排序将是错误的之后我插入约5000-10000新的随机整数。

我感谢你的任何意见。我不需要像一次又一次地重新排序另一种解决办法，因为我想改用System.arrayCopy的Arrays.sort。

注意：如果它的工作原理，它的1000倍，比Arrays.stream(...).sorted()更快，100倍比Arrays.sort再短路快

Answer 1

如果旧的指标是新的索引之前，那么实际的新的插入位置是一个都不能少。在代码：

void replace(int[] sorted, int oldValue, int newValue) {
    int oldI = Arrays.binarySearch(sorted, 0, sorted.length, oldValue);
    if (oldI < 0) { // Nothing to replace?
        return;
    }
    int newI = Arrays.binarySearch(sorted, 0, sorted.length, newValue);
    if (newI < 0) {
        newI = ~newI; // Insert position (when oldI not removed).
    }
    if (oldI < newI) { // oxxxx[n]
        --newI;
        System.arraycopy(sorted, oldI + 1, sorted, oldI, newI - oldI);
    } else if (oldI > newI) { // [n]xxxxo (newI points to first x).
        System.arraycopy(sorted, newI, sorted, newI + 1, oldI - newI);
    }
    sorted[newI] = newValue;
}

反相操作~相同x -> -x - 1。