Java-массивы Бинарный поиск

Question

У меня нет дополнительной информации о Arrays.binarySearch. Arrays.binarysearch точно, что они делают. Почему 3-3 консольный выход;

import java.util.*; 
    public class VLA2 implements Comparator<VLA2> { 
     int dishSize; 
     public static void main(String[] args) { 
      VLA2[] va = {new VLA2(40), new VLA2(200), new VLA2(60) ,new VLA2(70)}; 
      Arrays.sort(va, va[0]); 

      int index = Arrays.binarySearch(va, new VLA2(40), va[0]); 
      System.out.print(index + " "); 
      index = Arrays.binarySearch(va, new VLA2(69), va[0]); 
      System.out.print(index); 
     } 
     public int compare(VLA2 a, VLA2 b) { 
      return b.dishSize - a.dishSize; 
     } 
     VLA2(int d) { dishSize = d; } 
    } 

Answer 1

Ваш массив сортируется в {200, 70, 60, 40}, потому что ваш метод compare() возвращает положительное значение, когда a.dishSize < b.dishSize.

Поэтому, когда вы ищете Vla2 (40), вы найдете его в положении 3.

При поиске по Vla2 (69), он не нашел. Поэтому по определению возвращаемое значение метода равно -insertion_point - 1. В этом случае точка ввода будет равна 2, поэтому возвращаемое значение равно -3.

Метод Arrays.sort() сортирует по возрастанию. Но связь между членами определяется вашим компаратором. По определению, ваш компаратор должен возвращать отрицательное значение при < b и положительное значение при a> b. Если вы хотите, чтобы по возрастанию был естественным, измените свой метод compare(), чтобы вернуть a.dishSize - b.dishSize.

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

 int index = Arrays.binarySearch(va, new VLA2(40), va[0]); 

Здесь вы передаете в [0], а не использовать его в качестве значения Vla2, но и использовать его в качестве компаратора , Это может быть несколько запутанным.

Answer 2

После сортировки вашего массива он будет выглядеть как {200,70,60,40}, так как ваш компаратор сортируется в порядке убывания.

int index = Arrays.binarySearch(va, new VLA2(40), va[0]); 

Это будет возвращать индекс 40 в отсортированном массиве т.е. 3

В случае, если элемент не присутствует в массиве, метод BinarySearch будет возвращать (- (точка вставки) -1). Точка вставки - это индекс, в который должен быть вставлен элемент, чтобы сохранить массив в отсортированном порядке. Здесь

index = Arrays.binarySearch(va, new VLA2(69), va[0]); 

Чтобы сохранить массив отсортирован 69 должен быть вставлен в индекс = 2
{200,70,69,60,40} Таким образом, (-2) -1 = -3. Таким образом, двоичный поиск возвращает -3. Обратите внимание, что 69 не будут вставлены. Только точка ввода будет вычисляться функцией binarySearch.

Если вы ищете 269, Чтобы сохранить массив сортируется 269 должен быть вставлен в индекс = 0 {269,200,70,...} Так binarySearch() возвращает -0-1 = -1