Дает ли мне Arrays.binarySearch правильную позицию для отдельного элемента? - PullRequest
Новая
       7

Дает ли мне Arrays.binarySearch правильную позицию для отдельного элемента?

0 голосов
/ 07 февраля 2019

Я хотел бы использовать самый быстрый способ вставки новых элементов в отсортированный массив, и массив должен быть отсортирован после вставки.Поэтому я планировал использовать 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;

Javadoc из Arrays.binarySearch говорит: он возвращает индексключа поиска, если он содержится в массиве в указанном диапазоне;в противном случае (-(insertion point) - 1).Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента в диапазоне больше, чем ключ, или toIndex, если все элементы в диапазоне меньше указанного ключа.Обратите внимание, что это гарантирует, что возвращаемое значение будет >= 0 тогда и только тогда, когда ключ найден.

Я вставляю случайные целые числа [0..199], размер массива res равен 666.

Спорадически сортировка массива будет неправильной после того, как я вставлю около 5000-10000 новых случайных целых чисел.

Благодарю вас за любые советы.Мне не нужно другое решение, такое как повторная сортировка снова и снова, потому что я хочу использовать System.arrayCopy вместо Arrays.sort.

ПРИМЕЧАНИЕ. Если это работает, это в 1000 раз быстрее, чем Arrays.stream(...).sorted() и в 100 раз быстрее, чем повторное замыкание с Arrays.sort

1 Ответ

0 голосов
/ 07 февраля 2019

Если старый индекс находится перед новым индексом, то фактическая новая позиция вставки на единицу меньше.В коде: 

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.

...