정렬 된 목록에 재귀 적으로 삽입

Question

정수가 오름차순으로 정렬되었다고 가정하고 정렬 된 배열에 삽입하는 방법은 무엇입니까? 나는 바이너리 검색을 사용하라는 지시를 받았지만 엘리먼트의 위치 만 반환했다.

의사 코드의 예제는 grate가됩니다.

Answer 1

1. 사용 이진 검색 (이 링크 된 목록 인 경우, 매우 비싼 반복하는 수) 값이 동일한 경우 새로운 항목
2. 속한 위치를 찾을 수 - 할 아무것도
3. 경우] 값이 다르면 여기에 삽입해야합니다. 즉,이 위치에서 끝까지 모든 것을 다시 이동한다는 의미입니다 (링크 된 목록 인 경우 단순히이 시점에 새 노드를 삽입하면 모든 이동을 수행 할 필요가 없습니다)
4. 색인에 새 항목을 삽입하십시오.

Answer 2

예를 들어 정적 배열을 사용한다고 가정합니다. 어떤 목록에 연결하지

당신이 당신의 요구 사항에 따라 사용자 정의 할 수 있습니다 문자열 배열 할 수있는 방법입니다 다음

// 항목의 정렬 된 목록 문자열 [] 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; 
} 

는 숙제 후 숙제 태그를 추가한다