binarySearch二分查找API

看一个Demo

import java.util.Arrays; /** *@author Edward *@date 2020年7月3日---下午4:17:32 */ public class Demo09 { public static void main(String[] args) { /* * 二分查找API * Arrays.binarySearch(有序数组，被查找元素） * -如果找到，返回找到元素在数组中的位置 * -如果有重复元素，可能返回其中一个元素的位置 * -如果第一个元素，返回0 * -如果没有找到，则返回理想插入位置，值是-i-1 */ int[]arr = {2,5,6,34,56,56,88,88,94,95,100}; int i = Arrays.binarySearch(arr, 5); System.out.println(i);//1 i = Arrays.binarySearch(arr, 56); System.out.println(i);//5 i = Arrays.binarySearch(arr, 2); System.out.println(i);//0 // 如果找到，返回结果：0~n i = Arrays.binarySearch(arr, 20); // 插入位置为3 System.out.println(i);//-4=-3-1 -1是为了避免和0冲突 } }

源码是这样的：

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

很明显，将数组、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. }

找到了返回mid，没找到则是返回一个插入位置low处理后的结果-(low+1)。

这个返回值到底如何来用呢？

下面有个很好的场景：

在大量数据中查找某属性排名前100的数据

要求遍历一次即找出

下面来看代码：

import java.util.Arrays; import java.util.Random; /** * 在大量数据中查找某属性排名前100的数据 *@author Edward *@date 2020年7月3日---下午5:06:21 */ public class Demo10agag { public static void main(String[] args) { Random r = new Random(); int[]res = new int[100]; // 随机生成一个大量无序可重复的数组 int[]nums = new int[10000000]; for (int i = 0; i < 10000000; i++) { nums[i] = r.nextInt(10000000); } // 遍历一次即找出其中某属性排名前100的数据 for (int i = 0; i < nums.length; i++) { // 返回下标 int index = Arrays.binarySearch(res, nums[i]); // 边界条件判断，该数与res数组中最小的数相等或更小时，舍弃 if (index==0||index==-1) { continue; } // 转换 if (index<0) { index = -(index+1); } // 迭代腾出空间并插入 for (int j = 1; j < index; j++) { res[j-1]=res[j]; } res[index-1]=nums[i]; } System.out.println(Arrays.toString(res)); } }

这样，就很快地找到这100条数据。