【二分查找的实现方法----Java的binarySearch()方法】_java binarysearch

一、 二分查找简介：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。时间复杂度为O(logn)。
注意： 二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。这是实现二分查找的前提。（排序可以使用sort方法）

二、 二分查找的实现方法：

1、普通的迭代：

public static void main(String[] args) {
        int[] arr = {10,14,16,25,28,30,35,88,100};
        int index1 =binarySearch(arr,100);
        int index2 =binarySearch(arr,9);
        int index3 =binarySearch(arr,101);
        System.out.println("100的索引为："+index1);
        System.out.println("9的索引为："+index2)
        System.out.println("101的索引为："+index3);
    }
	//二分查找，递归方法
 	public  static int binarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length-1;
        while (low <= high){
            int mid = (low + high)/2;
            if (arr[mid] < key){
                low = mid+1;
            }else if (arr[mid] > key){
                high = mid -1;
            }else if (arr[mid] == key)
            return mid;
        }
        return -1;    
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运行结果：

100的索引为：8
9的索引为：-1
101的索引为：-1
1
2
3

可以看到在这种迭代的二分查找中，当查找元素在数组中则会返回它对应的下标，当元素不在数组中时，则统统返回-1；

2、普通的递归：

public static void main(String[] args) {
        int[] arr = {10,14,16,25,28,30,35,88,100};
        int index1 =binarySearch1(arr,100,0,arr.length-1);
        int index2 =binarySearch1(arr,9,0,arr.length-1);
        int index3 =binarySearch1(arr,101,0,arr.length-1);
        System.out.println("9的索引为："+index2);
        System.out.println("100的索引为："+index1);
        System.out.println("101的索引为："+index3);
    }
    //二分查找，递归方法
	public static int binarySearch1(int[] arr,int key,int low,int high){
        if (low > high)
            return -1;
        int mid = (low + high)/2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            return binarySearch1(arr,key,low,mid-1);
        else
            return binarySearch1(arr,key,mid+1,high);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

100的索引为：8
9的索引为：-1
101的索引为：-1
1
2
3

可以看到在这种递归的二分查找中，其运行结果与上面的迭代是一致的，只是传参时需要在后面加上查找的上界和下界，为它的递归提供条件。也是作为元素不存在的一个标志，即当上界小于下界时，数组内没有此元素，返回-1。

3、使用Java自带的方法——Arrays类的binarySearch方法：

（1）查找的过程：

每次对数组进行划分，选取中间的元素，让中间的元素与要查找的元素进行比较，然后不断修改其左右边界。

（2）方法的应用：

对于不同的情况，binarySearch方法会做出不同的反应，下面我将其分为两类进行学习：

a.数组内元素唯一：

public static void main(String[] args) {
		int[] arr = {1, 10, 23, 35, 55, 66, 88};
		//二分查找，binarySearch方法
		int index1 = Arrays.binarySearch(arr,66);
		int index2 = Arrays.binarySearch(arr,18);
		int index3 = Arrays.binarySearch(arr,-1);
		int index4 = Arrays.binarySearch(arr,99);
		System.out.println("66的索引值为：" + index1);
		System.out.println("18的索引值为：" + index2);
		System.out.println("-1的索引值为：" + index3);
		System.out.println("99的索引值为：" + index4);
	} 
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

66的索引为：5
18的索引为：-3
-1的索引为：-1
99的索引为：-8
1
2
3
4

从返回结果不难看出：
对于key是数组内存在的数，Arrays.binarySearch()方法会返回它对应的下标值。
而对key不是数组内存在的数的情况，分为三类：

• key不是数组内的数，但在这个有序数组的范围内 (arr[0] < key < arr[arr.length-1]) ：binarySearch返回的索引值为：- (应该插入的位置索引 + 1)；
• key不是数组内的数，且小于数组内最小的数 (key < arr[0]) ：
  binarySearch返回的索引值为：-1；
• key不是数组内的数，且小于数组内最小的数 (arr[arr.length-1] < key) ：
  binarySearch返回的索引值为：- (arr.length + 1)；

那么对于这些不存在数组内的元素，Arrays.binarySearch()方法为什么会分这么多情况，而不是像前两个一样只返回一个 -1呢？我将在后面的源码部分做出解释。

b.数组内元素存在重复值：

public static void main(String[] args) {
        //多个20
        int[] arr1 = new int[]{10,20,20,40,50,60};
        int index1 = Arrays.binarySearch(arr1,20);
        System.out.println("20的下标为："+index1);
        //多个10
        int[] arr2 = new int[]{10,10,20,40,50,60};
        int index2 = Arrays.binarySearch(arr2,10);
        System.out.println("10的下标为："+index2);
    }
1
2
3
4
5
6
7
8
9
10

运行结果：

20的下标为：2
10的下标为：0
1
2

这里也会出现一个神奇的现象，那就是在第一个数组中，返回的是第二个20，而在第一个数组中返回的是第一个10，这又是为什么呢？我也放在下面源码的分析中进行解释。

（3）源码的分析：

Arrays.binarySearch()方法的两种传参：

    //两个参数，数组a，和要查找的值key
public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
    //四个参数，在前两个的基础上，增加了两个值表示想要查找的区间段[fromIndex,toIndex]
public static int binarySearch(int[] a, int fromIndex, int toIndex,int key) {
        rangeCheck(a.length, fromIndex, toIndex);//此方法是用来检查给出的区间段是否会越界的
        return binarySearch0(a, fromIndex, toIndex, key);
    }
1
2
3
4
5
6
7
8
9

可以看到这两种传参最后都会去调用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

在这里我们可以看到这就是一个标准的二分查找的流程，但是它在返回上有点不同，当在数组中找不到想找的元素时，它返回的是 - (low + 1) ，并不是 -1，这也是导致对于这些不存在数组内的元素，Arrays.binarySearch()方法为什么会分这么多情况，而不是像前两个方法一样只返回一个 -1的原因。

a.对于第一个现象的解释：

• key不是数组内的数，但在这个有序数组的范围内：
  如在数组{1, 10, 23, 35, 55, 66, 88} 中找18一样：
  起始low = 0，high = 6。
  第一轮循环：mid = 3，midVal = a[3] = 35 > 18，high = mid - 1 = 2
  第二轮循环：mid = 1，midVal = a[1] = 10 < 18，low = mid + 1 = 2
  第三轮循环：mid = 2，midVal = a[2] = 23 > 18，high = mid - 1 = 1
  第四轮循环：此时low = 2 > high = 1，跳出while循环，返回 - (low +1) = - 3
  这也就是(2).a中18索引值的由来。
• key不是数组内的数，且小于数组内最小的数：
  如在数组{1, 10, 23, 35, 55, 66, 88} 中找-1一样：
  由于key = -1 < 1，所以它的low会一直为0，而high和mid会不断向0靠近，最终high = -1时跳出循环，返回的索引就为：- (low +1) = - (0 +1) = -1
• key不是数组内的数，且小于数组内最小的数：
  如在数组{1, 10, 23, 35, 55, 66, 88} 中找99一样：
  由于key = 99 > 88，所以它的high会一直为a.length - 1，而low和mid会不断向靠近arr.length - 1，最终low = a.length时跳出循环，返回的索引就为：- (low +1) = - (alength +1) = - 8

b.对于第二个现象的解释：

其实，不仅对于Arrays.binarySearch()方法会产生这样的现象，对于上面的迭代和递归遇到有重复数值的数组也会出现该问题。在Arrays.binarySearch()方法中其实有着一定的规律：

• 当数组长度为奇数时， 数组中有重复元素，Arrays.binarySearch()会优先返回奇数且靠近当前区间中间的下标
• 当数组长度为偶数时， 数组中有重复元素，Arrays.binarySearch()会优先返回偶数且靠近当前区间中间的下标

大家也可以尝试下自己写一个函数可以稳定获取重复值中下标小的那一个或者下标更大的。