Использование двоичного поиска для открытия пробела в массиве с правильным индексом

Question

Я должен создать два метода: Первый метод bSearch - это алгоритм двоичного поиска. Второй метод, insertInOrder, должен взять индекс, полученный из метода bSearch, и найти этот индекс в массиве, открыть пятно в этом индексе, сдвинув все остальные элементы этого массива и вставить ключ/int в этот индекс.

Эти данные будут получены из текстового файла, содержащего 25 целых чисел. Я не делаю никаких копий или дополнительных массивов, чтобы сделать это, и я должен кодировать и затем декодировать индекс в методе insertInOrder. В этих методах ключ будет текущим int, считываемым из файла int, и count будет подсчитывать количество полученных int. Я в основном создаю свой собственный метод сортировки, я не могу вызывать какие-либо внешние методы, и массив не должен быть в порядке в любое время.

Я заполнил эти методы, но я неловко понимаю. Я думаю, что моя проблема в том, что в методе bSearch, потому что я не могу заставить его возвращать что-либо, кроме 0. Я не могу заставить его вернуть новое значение mid, которое является индексом, где ключ/int должен быть вставлен. Чем ты за свою помощь. Код ниже:

static void insertInOrder(int[] arr, int count, int key ) 
    { 
     int index=bSearch(arr, count, key); 

     int encodedIndex = -(index+1); 
     int decodedIndex = -(index+1); 

     for (int i = index; i > 0; i--) 
     { 
      arr[i] = arr[i-1]; 
     } 

     arr[index]=key; 
    } 


    static int bSearch(int[] a, int count, int key) 
    { 
     int lo = 0; 
     int hi = a.length-1; 
     int index = 0; 
     boolean found = false; 
     while (!found && lo <= hi) 
     { 
      int mid = lo + ((hi - lo)/2); 
      if (a[mid] == key) 
      { 
       found = true; 
       index = mid;   
      } 
      else if (a[mid] > key) 
      { 
       hi = mid -1; 
      } 
      else 
      { 
       lo = mid +1; 
      } 
     } 
     return index; 
    } 

Answer 1

Ваш метод двоичного поиска работает правильно для предварительно заполненного массива.

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

В этом случае вам, вероятно, потребуется отслеживать, сколько значений используется в массиве. Это то, что означает значение «count»? В этом случае вы должны начать свое «привет» значение в счетчике вместо максимальной длины, и вам нужно вернуть счет в качестве индекса, если вы достигли конца массива, не найдя значения.

Обновление: вы можете использовать этот двоичный поиск, чтобы вернуть позицию вставки.

int lo = 0; 
    int hi = count-1; 
    int index = 0; 
    boolean found = false; 
    while (!found && lo < hi) 
    { 
     int mid = lo + ((hi - lo)/2); 
     if (a[mid] == key) 
     { 
      found = true; 
      index = mid; 
     } 
     else if (a[mid] > key) 
     { 
      hi = mid; 
      index = hi; 
     } 
     else 
     { 
      lo = mid +1; 
      index = lo; 
     } 
    } 
    return index;