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

Question

I would like to use the fastest way to insert new elements into a sorted array and the array must be sorted after insertion. So I have planned that I use System.arrayCopy, but sometimes I compute the wrong interval positions.

Here is my code:

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;

Javadoc of Arrays.binarySearch says: it returns index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

I insert random integers [0..199], the array size of res is 666.

Sporadically the sorting of the array will be wrong after I insert about 5000-10000 new random integer.

I thank you for any advice. I don't need another solution like re-sorting again and again, because I want to use System.arrayCopy instead of 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

If the old index is before the new index, then the actual new insert position is one less. In code:

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;
}

The invert operator ~ is the same as x -> -x - 1.