Arrays.binarySearch 博客分类: java基础 ArraysbinarySearch
今天在开发时,要判断一个逗号分隔的字符串中是否包含指定的字符串,考虑到aaa,aaa10,aaa11这种字符串无法正确判断aaa是否存在。因此先将调String的split方法将其转换成字符串数组。然后再用for循环或ArrayUtils.contains判断即可,后来在使用时发现Array.binarySearch(arr,obj)方法,虽然二分法查找需要被查找的数组已经是排好序的,但每次将查找范围缩小一半,元素比较的效率大大提高。特别越往后,二分法的耗时基本不变,而用contains()比较的耗时越来越大。
一.public static int binarySearch(int[] a, int key)说明
使用二进制搜索算法来搜索指定的 int 型数组,以获得指定的值。
必须在进行此调用之前对数组进行排序(通过上面的 sort 方法)。如果没有对数组进行排序,则结果是不明确的。
如果数组包含多个带有指定值的元素,则无法保证找到的是哪一个。
参数: a - 要搜索的数组。 key - 要搜索的值。
返回: 搜索键的索引,如果它包含在列表中;否则返回 (-(插入点) - 1)。
插入点被定义为将键插入列表的那一点:即第一个大于此键的元素索引,如果列表中的所有元素都小于指定的键,则为 list.size()。
注意,这保证了当且仅当此键被找到时,返回的值将 >= 0。 另请参见: sort(int[])
二.实例说明如果没有对数组进行排序,则结果是不明确的
字符串“218”在字符串“2180,2180,218,2180,21820,2180,2181,217”中,但如果没有对数组进行排序,其返回-1,表明未包含在列表中。
import java.util.Arrays; public class BinarySearchTest { public static void main(String[] args) { String code = "218"; String str = "2180,2180,218,2180,21820,2180,2181,217"; String[] dArray = str.split(","); int res = Arrays.binarySearch(dArray, code); System.out.println(res); } }
运行结果:-1
而经过Arrays.sort(dArray)排序后,结果运行正确。
import java.util.Arrays; public class BinarySearchTest { public static void main(String[] args) { String code = "218"; String str = "2180,2180,218,2180,21820,2180,2181,217"; String[] dArray = str.split(","); Arrays.sort(dArray); int res = Arrays.binarySearch(dArray, code); System.out.println(res); } }
运行结果:1
三.比较测试一下Arrays.binarySearch、list.contains两种方法的效率差异
package com.bijian.study; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class EffCompare { public static void main(String[] args) { List list = new ArrayList(10000); for(int i=0;i<100000;i++){ list.add("jack"+i); } String[] array = (String[]) list.toArray(new String[10000]); Arrays.sort(array); long begin = System.currentTimeMillis(); for(int k=60000;k<70000;k++){ //1 int index = Arrays.binarySearch(array, "jack"+k); //System.out.println(Arrays.binarySearch(array, "jack"+k)); } long end = System.currentTimeMillis(); System.out.println("二分法查找10000个item消耗:"+(end-begin)+"毫秒"); begin = System.currentTimeMillis(); for(int n=60000;n<70000;n++){ //2 boolean iist = list.contains("jack"+n); //System.out.println(list.contains("jack"+n)); } end = System.currentTimeMillis(); System.out.println("contains查找10000个item消耗:"+(end-begin)+"毫秒"); } }运行结果:
二分法查找10000个item消耗:8毫秒 contains查找10000个item消耗:14174毫秒测试的时候可以将 1,2 处的代码改为for(int n=0;n<10000;n++){,for(int n=90000;n<100000;n++){,可以发现,起始值越往后,二分法的耗时基本不变,而用contains()比较的耗时越来越大,原因当然是contains方法进行了越来越多的equals()调用(需要不断的调用equals()方法来比较这个对象和String[]中或List中的元素对象是否相等)。
上一篇: c# mutex互斥量的深入解析
推荐阅读
-
数组应用实战 博客分类: java Java数组Arrays
-
Arrays 博客分类: java.util Arrays
-
23种设计模式 博客分类: 设计模式 java设计模式
-
Arrays.binarySearch 博客分类: java基础 ArraysbinarySearch
-
JavaWeb面试那些事 博客分类: java面试 java面试javajavawebhibernate
-
java编程思想笔记(六)接口和抽象类 博客分类: java编程思想笔记 javajavawebjava编程思想
-
java编程思想练习题-第2章练习10 博客分类: javajava编程思想课后题 javajava编程思想
-
Java编程思想 博客分类: Book Java编程思想集合多线程框架容器
-
java编程思想笔记(二)一切都是对象 博客分类: javawebjava编程思想笔记 java编程
-
java动态表单设计解析 博客分类: java java 动态表单 formdesign 雷劈网