Java Arrays.binarySearch() 方法

 Java 数组常用方法

Java  Arrays.binarySearch()方法是java中的数组方法，用于搜索数组中的指定元素的位置。使用的是二分查找的算法。

它是jdk的原生方法，位于包 java.util。

语法

它有两种类型的语法，参数数量有所不同，这里以 int 类型为例，其语法如下: 

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

• 第一种语法：从索引0开始搜索元素key；
• 第二种语法：从范围[fromIndex, toindx)搜索元素key。

参数

• a：指定要搜索的数组
• key：指定要搜索的元素
• fromIndex: 指定要搜索的开始位置，闭区间包含
• toIndex: 指定要搜索的结束位置，开区间不包含

返回值

返回类型是int，返回元素的位置，若没有找到返回负值 -(low + 1) 。

什么意思？

比如有元素1，3，5，7，9

• 查找元素4，4在3的后面，下标为2，返回值为 -(2+1)= - 3
• 查找元素8，8在7的后面，下标为4，返回值为 -(4+1)= - 5

注意点

1. 使用的是二分查找算法
2. 使用该方法之前需要对数组排序，或者数组本来就是有序的。

例子

这里介绍两个例子，了解上面两种语法的使用。

例1

第一种语法的例子

import java.util.Arrays;

public class ArraBinarySearchExample{
    public static void main(String[] args) {

        int[] array = new int[]{1, 2, 3, 5, 7, 9};

        int i1 = Arrays.binarySearch(array, 3);
        int i2 = Arrays.binarySearch(array, -1);
        int i3 = Arrays.binarySearch(array, 4);
        int i4 = Arrays.binarySearch(array, 8);

        System.out.println("搜索元素3的位置："+i1);
        System.out.println("搜索元素-1的位置："+ i2);//-1下标为0 返回值为 -(0+1) = -1
        System.out.println("搜索元素4的位置："+ i3);// 4的下标为3 返回值为 -(3+1)= -4
        System.out.println("搜索元素8的位置："+ i4);// 8的下标为5 返回值为 -(5+1)= -6

    }
}

输出：

例2

第二种语法的例子

import java.util.Arrays;

public class ArrayBinarySearchExample2{
    public static void main(String[] args) {

        int[] array = new int[]{1, 2, 3, 5, 7, 9};

        //查找区间为 [a,b)
        int i1 = Arrays.binarySearch(array, 0,1, 3);
        int i2 = Arrays.binarySearch(array, 0,3, 3);

        System.out.println("搜索元素3的位置："+i1);
        System.out.println("搜索元素3的位置："+i2);

    }
}

输出:

内部实现

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

public static int binarySearch(int[] a, int fromIndex, int toIndex,
							   int key) {
	rangeCheck(a.length, fromIndex, toIndex);
	return binarySearch0(a, fromIndex, toIndex, key);
}

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.
}