Arrays类的binarySearch()方法详解_arrays.binarysearch

Arrays类的binarySearch()方法，可以使用二分搜索法来搜索指定的数组，但数组必须有序。

遇到的问题：在int数组逆序的情况下返回索引与实际索引不符（查询数在数组内）
测试的binarySearch方法申明public static int binarySearch(int[] a, int key)

测试代码：

public class Test {
    public static void main(String[] args) {
        int[] arr01 = {1,2,3,4,5};
        int[] arr02 = {5,4,3,2,1};
        int search = Arrays.binarySearch(arr01,5);
        search = Arrays.binarySearch(arr01,5);
        System.out.println("index="+search);
    }
}
1
2
3
4
5
6
7
8
9

1.数组从小到大排序时运行结果：(使用数组arr01测试)

这里符合预期，正确无误。

2.数组从大到小排序时运行结果：(使用数组arr02测试)

可以看到数组有序且5在数组内，但binarySearch()返回的值不是预期值。

以下时调用binarySearch()源码

1. 首先程序调用binarySearch()

int[] arr02 = {5,4,3,2,1};
        int search = Arrays.binarySearch(arr02,5);
1
2

2. 进入binarySearch()查看实现过程

    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
1
2
3

3. 从源码来看binarySearch()方法调用了binarySearch0()的方法

//binarySearch()的源码（int的binarySearch源码）
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
//方法定义
private static int binarySearch0(int[] a, int fromIndex, 
								 int toIndex,int key)
1
2
3
4
5
6
7

从定义可以看出binarySearch0()方法有四个参数

• 第一个参数：需要查询的数组（源数组）
• 第二个参数：从源数组中那个索引开始查找
• 第三个参数：源数组中停止查找索引
• 第四个参数：需要查找的值

4. binarySearch0()源码

    private static int binarySearch0(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.
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

回忆测试数据:

 int[] arr02 = {5,4,3,2,1};
 int search = Arrays.binarySearch(arr02,5);
1
2

调用binarySearch方法内调用binarySearch0方法并且传值为【a, 0, a.length, key】
【>>>：“无符号”右移位运算符(>>>)，它使用了“零扩展”：无论正负，都在高位插入0】

binarySearch0()方法中fromIndex初始化为0，high初始化为a.length-1

第一次循环：
low <= high成立(0<4)进入循环体内，mid被赋值为(low + high) >>> 1）=（0+4）/2=2，midVal = a[mid]=3；
开始判断midVal < key 等价于 3<5 成立，执行low = mid + 1，low被赋值为3了但是数组中5 的索引为0，此刻二分查找已经忽略前半部分直接去查找后半部分有没有5，而它返回的值是：当数据5没有应该插入哪里。

测试的是public static int binarySearch(int[] a, int key)方法
因此提出binarySearch方法是否可以查询逆序的数组元素？