ソートされたリストに再帰的に挿入

Question

整数が昇順にソートされていると仮定すると、ソートされた配列にどのように挿入しますか？バイナリ検索を使用するように言われましたが、要素の位置だけが返されます。

擬似コードの例はgrateです。

Answer 1

1. 値が同じであれば、新たなアイテムが
2. に属し場所を見つけるために、（これは、リンクされたリストである場合には、非常に高価反復することができる）のバイナリ検索を使用する - 場合は何も
3. もしません値は異なります。ここに挿入する必要があります。これは、すべてをこの位置から最後に移動することを意味します（リンクされたリストの場合は、単にこの時点で新しいノードを挿入することを意味します）
4. 新しい項目をインデックスに挿入します。

Answer 2

たとえば、静的配列を使用しているとします。何のリストリンクされていない

あなたの要件ごとにカスタマイズすることができます文字列配列で行う方法を以下に示します

//項目の順序付きリスト のString [] sortedArray =新しいString [] { "アリとanarrayを作成します。 "、"バット "、"猫 "、"犬 "};

// 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