вставка в отсортированный список рекурсивно

Question

Как бы вы вставили в отсортированный массив, предполагая, что целые числа были отсортированы в порядке возрастания.Мне сказали использовать бинарный поиск, но это будет только возвращать позицию элемента.

Примером в псевдокоде было бы здорово.

Answer 1

1. используйте бинарный поиск (если это связанный список, итерация может быть довольно дорогой), чтобы найти место, где новые элементы принадлежат
2. , если значение одинаковое - ничего не делать
3. Если значение отличается, нужно вставить сюда, что означает перемещение всего назад из этой позиции в конец на единицу (если это связанный список, просто означает вставку нового узла в этой точке, не иметьсделать все изменения)
4. вставить новый элемент в указатель.

Answer 2

Предполагается, что вы используете статический массив, например нет связанного списка

Ниже приведен способ обработки массива строк, который вы можете настроить в соответствии с вашими требованиями

// Создать анарай с упорядоченным списком элементов String [] sortedArray = new String [] {"ant", "bat", "cat", "dog"};

// Search for a non-existent item and then insert it
int index = Arrays.binarySearch(sortedArray, "cow");
if (index < 0) {
    // Compute the insert index
    int insertIndex = -index-1;

    // Insert the new item into sortedArray. The example here creates
    // a new larger array to hold the new item.
    String[] newSortedArray = new String[sortedArray.length+1];
    System.arraycopy(sortedArray, 0, newSortedArray, 0, insertIndex);
    System.arraycopy(sortedArray, insertIndex,
                     newSortedArray, insertIndex+1,
                     sortedArray.length-insertIndex);
    newSortedArray[insertIndex] = "cow";
    sortedArray = newSortedArray;
}

см. http://www.exampledepot.com/egs/java.util/coll_InsertInArray.html