Двоичный поиск и вставка сортировки

Question

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

static void insertInOrder(int[] arr, int cnt, int newVal) { 

    int index = bSearch(arr, 0, arr.length-1, newVal) ; 
    if (index < 0) { 
     index = -1 - index ; 
    } 
    for (int i = cnt; i >= index+1 ; --i) { 
     arr[i] = arr[i-1]; 
    } 

    arr[index] = newVal; 
} 


public static int bSearch(int[] a, int lo, int hi, int key) { 
    int mid = (lo+hi)/2; 
    if(lo>hi) 
     return -1; 
    else if (a[mid]==key) 
     return mid; 
    else if (a[mid]<key) 
     return bSearch(a, mid+1, hi, key); 
    else 
     return bSearch(a, lo, mid-1, key); 
} 

---

Reading in: 5 13 7 9 21 
Current Output: 21 9 7 13 5 
Desired Output: 5 7 9 13 21 

---

Это insertInOrder в мой главный

int[] arr = new int[INITIAL_CAP]; 
    int arrCnt= 0; 
    while (infile.hasNextInt()) 
    { 
     if (arrCnt==arr.length) 
      arr = doubleMyLength(arr); 
     insertInOrder(arr, arrCnt, infile.nextInt()); 
     ++arrCnt; 
    } 
    infile.close(); 

    arr = trimMyLength(arr, arrCnt); 
    System.out.println("Sorted array of " + arr.length + " ints from " + args[0] + " after insert in order:"); 
    printArray(arr); // we trimmed it so count == length so we don't bother to pass in count 

Answer 1

Когда newVal не найден в массиве (что довольно вероятно, произойдет), ваши bSearch() возвращается -1 , Затем insertInOrder() всегда вставляют элемент в позицию index = -1 - index, то есть 0. Вот почему результат ошибочен.

Чтобы получить его правильно, необходимо вернуть наименьший индекс, в котором значение больше newVal.

Answer 2

В коде есть две проблемы. Один из них, как указано в @timrau, заключается в том, что вы возвращаете неправильное значение -1 из метода двоичного поиска, если запись не найдена. Вы должны вернуть -lo - 1. (Это то место, где вы должны вставить значение - возврат отрицательного значения используется для указания того, что значение не было найдено в двоичном поиске. Но в вашем случае вам не нужно получать дубликаты в отсортированном списке, поэтому вы также можете сразу вернуть lo.)

Во-вторых, вы передаете неправильную длину массива вашему двоичному методу поиска. Он должен быть cnt - 1, а не arr.length - 1.

код становится:

static void insertInOrder(int[] arr, int cnt, int newVal) { 
    int index = bSearch(arr, 0, cnt - 1, newVal); 
    if (index < 0) { 
     index = -1 - index; 
    } 
    for (int i = cnt; i >= index + 1; --i) { 
     arr[i] = arr[i - 1]; 
    } 

    arr[index] = newVal; 
} 

public static int bSearch(int[] a, int lo, int hi, int key) { 
    int mid = (lo + hi)/2; 
    if (lo > hi) 
     return -lo - 1; 
    else if (a[mid] == key) 
     return mid; 
    else if (a[mid] < key) 
     return bSearch(a, mid + 1, hi, key); 
    else 
     return bSearch(a, lo, mid - 1, key); 
}