当找不到结果时,二进制搜索的输出奇怪

Question

当找不到结果时,我得到一个奇怪的输出.

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

public class BinarySearch {

    public static void main(String args[]) {
        String arr[] = { "c", "a", "e", "f", "z" };
        MySort ms = new MySort();
        Arrays.sort(arr, ms);

        for (String c : arr) {
            System.out.println(c);
        }

        System.out.println(Arrays.binarySearch(arr, "b", ms));

    }

    static class MySort implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            return o2.compareTo(o1);
        }

    }

}

输出: zfeca-6

-2当我将"y"作为查询参数-5传递给我时,为什么会打印出来b.如果找不到结果,任何人都可以让我知道发生了什么.

Answer 1

我不太了解Java,但谷歌给了我这个链接.

如果搜索失败,则返回值表示插入点 - 您可以插入搜索项的索引,它会保留排序顺序.因此,您可以将其与成功结果区分开来,插入点值始终为负值.

实际的回报值是-(insertpoint) - 1.如果你知道你的二进制补码(有符号整数的二进制表示),你会认为这是插入点的按位而不是.这个值有点令人感兴趣,因为任何特定位宽的每个可能的非负整数都有一个负的位补码(翻转所有位,包括符号位).

Answer 2

Arrays#binarySearch()返回元素的索引要搜索，或者如果没有找到，则返回(-index - 1)，其中index是其中元件将排序后的数组中插入的位置。

从文档：

返回：
搜索关键字的索引，如果它包含在数组中；否则，(-(insertion point) - 1)。插入点定义为将键插入数组的点：大于键的第一个元素的索引，如果数组中的所有元素都小于指定的键，则为 a.length。请注意，这保证了>= 0当且仅当找到键时返回值。

现在，你的数组排序，"b"将在插入index = 1后右"a"。因此返回值是(-1 - 1) = -2