Сортировка массива с использованием binarySearch

Question

Я просто хочу спросить, почему я все еще получаю нулевой указатель на свою функцию sortInOrder(Object x).

То, что я пытаюсь сделать, это использовать sortInOrder для вставки объектов в мой массив data[] в порядке возрастания.

public Object[] data = new Object[10]; 

public static void main(String[] args) { 

    for (int i = 0; i < 5; i++) 
    { 
     int r = (int) (Math.random() * 100); 
     System.out.println("Adding " + r); 
     sortInOrder(r); 

     for (int j = 0; j <= 10; j++) 
      System.out.println((Integer) data[j]); 
    } 

    for (int i = 0; i < 10; i++) 
     System.out.println((Integer) data[i]); 
} 

public static void sortInOrder(Object x) { 
    if (x == null) 
     throw new IllegalArgumentException(); 

    int idx = 0; 
    if (data[idx] != null) 
     idx = Arrays.binarySearch(data, 0, data.length-1, ((Integer) data[idx]).compareTo((Integer) x)); 

    for (int i = idx + 1 ; i < data.length - 1 ; i++) 
     data[i] = data[ i - 1 ]; 

    data[idx] = x; 
} 

Answer 1

Я исправил ваш код. Обратите внимание, что возвращаемое значение метода BinarySearch является:

«индекс ключа поиска, если оно содержится в массиве в пределах указанного диапазона, в противном случае, (- (точка вставки) - 1)» (source)

import java.util.Arrays; 
import java.util.Comparator; 

public class Q1 { 

    public static Object[] data = new Object[10]; 

    public static void main(String[] args) { 

     for (int i = 0; i < 5; i++) { 
      int r = (int) (Math.random() * 100); 
      System.out.print("Adding: " + r); 
      sortInOrder(r); 

      System.out.print("["); 
      for (int j = 0; j < 10; j++) 
       System.out.print(" " + data[j]); 
      System.out.println(" ]"); 
     } 

     System.out.print("["); 
     for (int i = 0; i < 10; i++) 
      System.out.print(" " + data[i]); 
     System.out.print(" ]"); 
    } 

    public static void sortInOrder(Integer x) { 
     if (x == null) 
      throw new IllegalArgumentException(); 

     int idx = Arrays.binarySearch(data, 0, data.length - 1, x, Comparator.nullsLast((Object o1, Object o2) -> ((Integer) o1) - ((Integer) o2))); 

     if (idx < 0) idx = -idx - 1; 
     System.out.println(" at index: " + idx); 

     // Hint: Use arraycopy instead of for loop for better performance 
     System.arraycopy(data, idx, data, idx + 1, data.length - 1 - idx); 

     data[idx] = x; 
    } 

} 

в качестве альтернативы Вы можете использовать анонимный класс вместо лямбда:

int idx = Arrays.binarySearch(data, 0, data.length - 1, x, 
    Comparator.nullsLast(new Comparator<Object>() { 
     @Override 
     public int compare(Object o1, Object o2) { 
      return ((Integer) o1) - ((Integer) o2); 
     } 
    })); 

Результат:

Adding: 2 at index: 0 
[ 2 null null null null null null null null null ] 
Adding: 29 at index: 1 
[ 2 29 null null null null null null null null ] 
Adding: 88 at index: 2 
[ 2 29 88 null null null null null null null ] 
Adding: 9 at index: 1 
[ 2 9 29 88 null null null null null null ] 
Adding: 27 at index: 2 
[ 2 9 27 29 88 null null null null null ] 
[ 2 9 27 29 88 null null null null null ] 
Process finished with exit code 0