Arrays.binarysearch (double [] array, key) return -1

Question

Я написал небольшой фрагмент кода, чтобы определить индекс следующего меньшего элемента в массиве. Фрагмент кода ниже:

public static int FindNextSmallest(double[] arr1, int current_small_index) { 
    double current_smallest_element = arr1[current_small_index];  

    double[] new_arr1 = arr1.clone(); 

    Arrays.sort(new_arr1); 

    int v = Arrays.binarySearch(new_arr1, current_smallest_element); 

    double next_small = new_arr1[v + 1]; 
    int next_small_index = Arrays.binarySearch(arr1, next_small); 
    return next_small_index; 
} 

массив содержит значения: {0.6666,0.6666,0.6666, -0,9333, -0,9333}.

В начале current_small_index равно 3 с current_small_element = -0.9333, Затем он возвращает следующий наименьший элемент, который в этом случае равен -0.9333 в позиции индекса 4. Но он возвращает -1.

Пожалуйста, помогите.

Answer 1

В этом заявлении

int next_small_index = Arrays.binarySearch(arr1, next_small); 

Вы пытаетесь применить binarySearch к исходному несортированным массива. Метод двоичного поиска работает только на отсортированные массивы.

Answer 2

Вам не нужно делать это при сортировке и бинарном поиске, что равно O(n log n) во времени и O(n) на складе. Вы можете сделать это в O(n) времени и O(1) хранения, работая непосредственно на входном массиве:

int next_smallest_index = -1; 
for (int i = 0; i < arr1.length; ++i) { 
    if (i == current_smallest_index) continue; 

    if (arr1[i] >= arr1[current_smallest_index]) { 
    if (next_smallest_index == -1 || arr1[i] < arr1[next_smallest_index]) { 
     next_smallest_index = i; 
    } 
    } 
} 

Кроме того, это дает индекс элемента непосредственно: если вы отсортировали список, вы потеряли данные для заказа, поэтому вам нужно вернуться и найти элемент со значением, которое вы нашли.