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 说：它 returns 搜索键的索引，如果它包含在指定范围内的数组中；否则，(-(insertion point) - 1)。插入点定义为将键插入数组的点：范围内大于键的第一个元素的索引，或者 toIndex 如果范围内的所有元素都小于指定钥匙。请注意，当且仅当找到密钥时，这保证 return 值将是 >= 0。

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

在我插入大约 5000-10000 个新的随机整数后，数组的排序偶尔会出错。

谢谢你的建议。我不需要像一次又一次重新排序这样的其他解决方案，因为我想使用 System.arrayCopy 而不是 Arrays.sort.

NOTE: If it works, it's 1000 times faster than Arrays.stream(...).sorted(), and 100 times faster than re-shorting with 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 相同。

Arrays.binarySearch 是否为我提供了非包含元素的正确位置？

Does Arrays.binarySearch give me a right position of a non-contained element?

java

arrays

binary-search