java array search_Java中的Arrays.binarySearch()方法详解

1. 作用

通过二分法在已经排好序的数组中查找指定的元素，并返回该元素的下标

2. 操作接口

方法原型为：public static int binarySearch(Object[] a, Object key)，该函数需要接收两个参数：数组名称，以及我们所需要查找的元素

3. 返回值

该方法的返回值的类型为整型，具体返回值具体分为以下两种情况：

如果数组中存在该元素，则会返回该元素在数组中的下标

例如：

import java.util.Arrays;

public class binarySearch {

public static void main(String[] args) {

int[] scores = {1, 20, 30, 40, 50};

//在数组scores中查找元素20

int res = Arrays.binarySearch(scores, 20);

//打印返回结果

System.out.println("res = " + res);

}

}

运行结果：res = 2

如果数组中不存在该元素，则会返回 -(插入点 + 1)，

这里的插入点具体指的是：如果该数组中存在该元素，那个元素在该数组中的下标

例如：

import java.util.Arrays;

public class binarySearch {

public static void main(String[] args) {

int[] scores = {1, 20, 30, 40, 50};

//1.在数组scores中查找元素25

//从数组中可以看出 25位于20与30之间，

//由于20的下标为1，所以25的下标为2，

//最后的返回值就为：-(2 + 1) = -3

int res1 = Arrays.binarySearch(scores, 25);

//2.同理在该数组中查找-2

//可以看出-2比数组中的任何一个元素都要小

//所以它应该在数组的第一个，所以-2的下标就应该为0

//最后的返回值就为：-(0 + 1) = -1

int res2 = Arrays.binarySearch(scores, -2);

//3.又例如在该数组中查找55

//由于55比数组中的任何一个元素都要大

//所以他应该位于数组的最后一个，它的下标就为5

//最后的返回值就为：-(5 + 1) = -6

int res3 = Arrays.binarySearch(scores, 55);

//打印返回结果

System.out.println("res1 = " + res1);

System.out.println("res1 = " + res2);

System.out.println("res1 = " + res3);

}

}

运行结果：

res1 = -3

res1 = -1

res1 = -6

4. 具体实现原理

import java.util.Arrays;

public class binarySearch {

public static void main(String[] args) {

int[] scores = {1, 20, 30, 40, 50};

//调用java提供的binarySearch方法

int a = Arrays.binarySearch(scores, 30);

//调用自定义的binarySearch方法

int b = myBinarySearch(scores, 30);

System.out.println("a = " + a);

System.out.println("b = " + b);

}

//自定义二分查找函数

public static int myBinarySearch(int [] array, int key) {

int low = 0;

int high = array.length - 1;

int mid = (low + high) / 2;

while(low <= high) {

if(key < array[mid])

high = mid - 1;

else if(key > array[mid])

low = mid + 1;

else

return mid;

}

return -(1 + low);

}

}

运行结果：

a = 2

b = 2