Java 数组 binarySearch() 插入点
Java Arrays binarySearch() insertion point
根据 Java 文档 Arrays.binarySearch(int[] a, int key)
Returns:
index of the search key, if it is contained in the array;
otherwise, (-(insertion point) - 1). The insertion point is defined as
the point at which the key would be inserted into the array: the index
of the first element greater than the key, or a.length if all elements
in the array are less than the specified key. Note that this
guarantees that the return value will be >= 0 if and only if the key
is found.
我需要了解为什么它会返回 (-(insertion point) - 1)，为什么不只是 -(insertion point)？
因为如果它返回-(insertion point)，并且插入点是0，那么你将无法区分我找到了，它在索引0， 我没找到，你可以在索引 0.
处插入
考虑一个数组：
int intArr[] = {5,12,20,30,55};
现在考虑这两个二进制搜索语句：
System.out.println("The index of element 5 is : " + Arrays.binarySearch(intArr,5));
和
System.out.println("The index of element 4 is : " + Arrays.binarySearch(intArr,4));
输出
The index of element 5 is : 0
The index of element 4 is : -1
因为 -1，我们可以区分这两个输出。如果没有 -1 那么这两个语句都会给出相同的输出，即 0.
根据 Java 文档 Arrays.binarySearch(int[] a, int key)
Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
我需要了解为什么它会返回 (-(insertion point) - 1)，为什么不只是 -(insertion point)？
因为如果它返回-(insertion point)，并且插入点是0，那么你将无法区分我找到了，它在索引0， 我没找到，你可以在索引 0.
考虑一个数组：
int intArr[] = {5,12,20,30,55};
现在考虑这两个二进制搜索语句：
System.out.println("The index of element 5 is : " + Arrays.binarySearch(intArr,5));
和
System.out.println("The index of element 4 is : " + Arrays.binarySearch(intArr,4));
输出
The index of element 5 is : 0
The index of element 4 is : -1
因为 -1，我们可以区分这两个输出。如果没有 -1 那么这两个语句都会给出相同的输出，即 0.