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() 方法 return 在 a.dishSize < b.dishSize 时为正值。

因此，当您搜索 VLA2(40) 时，您会在位置 3 找到它。

当您搜索 VLA2(69) 时，找不到它。所以根据定义，方法的 return 值为 -insertion_point - 1. 在这种情况下，插入点为 2，因此 return 值为 -3.

Arrays.sort() 方法确实按升序排序。但是成员之间的关系是由你的比较器定义的。 根据定义，您的比较器必须 return 在 a < b 时为负值，在 a > b 时为正值。 如果您希望升序是自然的，请更改您的compare() 方法 return a.dishSize - b.dishSize.

顺便说一句，一个对象作为它自己的比较器是不寻常的。理想情况下 class 代表一个概念。在这种情况下，将两个概念混合为一个 class 会导致这样的调用：

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

在这里，您传递 va[0]，不是将其用作 VLA2 值，而是将其用作比较器。这可能有点令人困惑。

Answer 2

排序后你的数组看起来像 {200,70,60,40} 作为您的比较器按降序排序。

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

这将 return 排序数组中的索引 40 即 3

如果元素不存在于数组中，binarySearch 方法将 return (-(插入点) -1)。插入点是应该插入元素以保持数组有序的索引。这里

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

为了保持数组排序 69 应该插入到 index=2
{200,70,69,60,40} 所以 (-2)-1 = -3 。所以二进制搜索returns -3。请注意，不会插入 69。 binarySearch 函数只会计算插入点。

如果您要搜索 269，为了保持数组排序 269 应该插入到 index=0 {269,200,70,...} 所以 binarySearch() returns -0-1 = -1

Java 数组二进制搜索

Java Arrays Binary Search

java

arrays

sorting

arraylist

binary-search