Question

【JAVA】数组问题,请高手帮忙解决下我这个新手的疑惑

int arr[] = new int[]{4,25,10};
Arrays.sort(arr);
int index = Arrays.binarySearch(arr,0,1,8)

为什么index =-2 还有插入点"-"又是什么

这个知识点书上讲得不是很清楚,我想请高手详细的给我讲下这个知识点到底怎么回事

Answer 1

题主代码的插入点为1，arr排序后为{4, 10, 25}，key=8，搜索范围为[0,1)，在该范围内只有4这一元素，范围中的元素没有任何一个大于8，那么，此时8应当插到范围中的最后一个元素之后，即索引为1的位置，则插入点为1，所以返回结果 = -(1) -1 = -2。

看文档上的解释：

public static int binarySearch(int[] a,
int fromIndex,
int toIndex,
int key)

使用二分搜索法来搜索指定的 int 型数组的范围，以获得指定的值。必须在进行此调用之前对范围进行排序（通过 sort(int[], int, int) 方法）。如果没有对范围进行排序，则结果是不确定的。如果范围包含多个带有指定值的元素，则无法保证找到的是哪一个。

参数：
a - 要搜索的数组
fromIndex - 要搜索的第一个元素的索引（包括）
toIndex - 要搜索的最后一个元素的索引（不包括）
key - 要搜索的值

返回：
如果它包含在数组的指定范围内，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点
被定义为将键插入数组的那一点：即范围中第一个大于此键的元素索引，如果范围中的所有元素都小于指定的键，则为 toIndex。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。

追问

也就是用这个方法之前必须排序不然就无发正常的使用该方法是吗

指定键就是要搜索的键把,

另外,语法结果是规定如果没有一个是要找的键 返回结果 = -(插入点) -1 =几 是这样吗

还有为什么保证了当且仅当此键被找到时，返回的值将 >= 0。

追答

是的。使用二分搜索必须先排序，不然结果将是不确定的。(-(插入点) - 1) 就是一个加减运算。

至于“为什么保证了当且仅当此键被找到时，返回的值将 >= 0”。这个简单啊，找到要搜索的键了，说明这个键就在数组中了，该方法就返回它的索引值了，索引值当然是 >= 0 的。如果没有找到，方法就返回(-(插入点) - 1) ，而插入点也是索引值，也是 >= 0 的，算下来不就 = 0，否则返回的值将 < 0。”

追问

没找到不是返回-1或返回"-"(插入点)

什么情况返回结果"-"(插入点)

这里返回-2又是什么机制,书上讲得模拟两可的,我实在不是很懂,混乱的.

插入点就是搜索范围的末端第一个比末端索引大的那个把?

追答

我给你的文档片段已经说得很清楚了，没有找到的话返回的是(-(插入点) - 1)，不会返回(-(插入点))。返回-1是当插入点=0的时候，(-(0)-1)=-1。

    “插入点被定义为将键插入数组的那一点：即范围中第一个大于此键的元素索引，如果范围中的所有元素都小于指定的键，则为 toIndex。”

    这已经说得很清楚了，插入点就是如果将你要搜索的键插入到数组中时应该插入到的位置。对于数组{4, 10, 25}，键为8的二分搜索，但是键没有被找到，如果要把该键插入到此数组中的话，它就应当插到元素4之后，元素10之前。插入之后数组{4, 8, 10, 25}，此时数组该键的索引值就是插入点的值 = 1。

    而你题中的代码里，对数组的二分搜索是有范围的，那你就把范围中的元素拿出来当成一个新的数组进行二分搜索不就成了吗？题中给的范围是[0,1)，把该范围的所有元素拿出来组成一个新的数组：{4}，再在这个数组里搜索8，但是没有找到，这时候如果把8插入这个数组中的话应该插到元素4之后：{4, 8}，此时8的插入位置的索引值=1，那么插入点=1。方法的返回值=(-(插入点) - 1)=(-(1) - 1)=-2。题中-2就是这么来的。

看文档吧，理解文档的说明，实在不行就写例子运行，多验证、理解。要么看源码：

static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Answer 2

以上是复制的中文api,很明显你的代码中在数组中找8,找不到,所以  " 插入点"  为1,所以你的index的值为-2.

(看明白"插入点"的定义).

Answer 3

Arrays.binarySearch是进行二分查找
binarySearch(object[ ], object key);
如果key在数组中，则返回搜索值的索引；否则返回-1或者"-"(插入点)。插入点是索引键将要插入数组的那一点，即第一个大于该键的元素索引。
binarySearch(object[ ], int fromIndex, int endIndex, object key);
如果要搜索的元素key在指定的范围内，则返回搜索键的索引；否则返回-1或者"-"(插入点)。
Arrays.binarySearch(arr,0,1,8)的意思是查找范围从数组arr的下标为0的元素开始到下标为1的元素结束，查找8这个数，如果8在arr数组中，返回8的下标；如果没有，返回一个负数。

手头准备一个API文档，不懂的随时查