对一个列表进行检索时,我们使用的最多的是indexOf方法,它简单好用,而且也不会出错,虽然它只能检索到第一个符合条件的值,但是我们可以生成子列表后再检索.这样也就可以查找到所有符合条件的值了.
Collections工具类也提供了一个检索的方法:binarySearch,这个是干什么的?该方法也是对一个列表进行检索的,可以查找出指定的索引值,但是在使用这个方法时就有一些注意事项,看代码:
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.List; 4 5 public class Client { 6 public static void main(String[] args) { 7 List<String> cities = new ArrayList<String>(); 8 cities.add("上海"); 9 cities.add("广州"); 10 cities.add("广州"); 11 cities.add("北京"); 12 cities.add("天津"); 13 //indexOf方法取得索引值 14 int index1 = cities.indexOf("广州"); 15 //binarySearch查找到索引值 16 int index2 = Collections.binarySearch(cities, "广州"); 17 System.out.println("索引值(indexOf)："+index1); 18 System.out.println("索引值（binarySearch)："+index2); 19 } 20 }
运行结果:
索引值(indexOf)：1
索引值（binarySearch)：2
结果不一样,虽然有两个"广州"这样的元素.但是返回的结果都应该是1才对,为何binarySearch返回的结果是2,问题就出现在2分法搜索上,二分法搜索就是"折半折半再折半"简单,效率高.
看JDK中源码是如何实现的:
1 private static final int BINARYSEARCH_THRESHOLD = 5000; 2 public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { 3 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 4 return Collections.indexedBinarySearch(list, key);//随机存取列表或者元素数量少于5000的顺序列表 5 else 6 return Collections.iteratorBinarySearch(list, key);//元素数量大于50000的顺序存取列表 7 }
ArrayList实现了RandomAccess接口,是一个顺序存取列表,使用了indexBinarySearch方法,代码如下:
1 private static <T> 2 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) 3 { 4 int low = 0;//默认上界 5 int high = list.size()-1;//默认下界 6 7 while (low <= high) { 8 int mid = (low + high) >>> 1;//中间索引,无符号右移1位 9 Comparable<? super T> midVal = list.get(mid);//中间值 10 int cmp = midVal.compareTo(key);//比较中间值 11 //重置上界和下界 12 if (cmp < 0) 13 low = mid + 1; 14 else if (cmp > 0) 15 high = mid - 1; 16 else 17 return mid; // key found 找到元素 18 } 19 return -(low + 1); // key not found 没有找到元素,返回负值 20 } 21 22 private static <T> 23 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) 24 { 25 int low = 0; 26 int high = list.size()-1; 27 ListIterator<? extends Comparable<? super T>> i = list.listIterator(); 28 29 while (low <= high) { 30 int mid = (low + high) >>> 1; 31 Comparable<? super T> midVal = get(i, mid); 32 int cmp = midVal.compareTo(key); 33 34 if (cmp < 0) 35 low = mid + 1; 36 else if (cmp > 0) 37 high = mid - 1; 38 else 39 return mid; // key found 40 } 41 return -(low + 1); // key not found 42 }
以上就是二分法搜索的Java版实现,首先是获得中间索引值,我们的例子中是2,那么索引值是2的元素值是多少?正好是"广州",于是返回索引值2.正确没有问题.
那么再看indexOf的实现:
1 public int indexOf(Object o) { 2 if (o == null) { 3 for (int i = 0; i < size; i++) 4 if (elementData[i]==null) 5 return i; 6 } else { 7 for (int i = 0; i < size; i++) 8 if (o.equals(elementData[i])) 9 return i; 10 } 11 return -1; 12 }
indexOf方法就是一个遍历,找到第一个元素值相等则返回.
两者的算法都没有问题,是我们用错了binarySearch的用法,因为二分法查询要有一个首要的前提,数据集已经实现了升序排列,否则二分法查找的值是不准确的.不排序怎么确定是在比中间值小的区域还是比中间值大的区域呢?
二分法排序首先要排序,这是二分法的首要条件.
问题清楚了,使用Collection.sort排序即可,但是这样真的可以解决吗?元素数据是从Web或数据库中传过来的,原本是一个有规则的业务数据,为了查找一个元素对其排序,改变了元素在列表中的位置.那谁来保证业务规则的正确性呢?
所以binarySearch在此处首先了.当然可以拷贝一个数组,然后再排序,再使用binarySearch查找指定值,也是可以解决问题.
当然使用binarySearch的二分法查找比indexOf遍历算法性能上高很多,特别是在大数据集而且目标值又接近尾部时,binarySearch方法与indexOf相比,性能上会提升几十倍,因此在从性能的角度考虑时可以选择binarySearch.
//==================测试binarySearch()和indexOf的时间=========
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.List; 4 5 6 public class Client { 7 public static void main(String[] args) { 8 int max =1200000; 9 List<String> cities = new ArrayList<String>(); 10 for(int i=0;i<max;i++){ 11 cities.add(i+""); 12 } 13 //indexOf方法取得索引值 14 long start = System.nanoTime(); 15 int index1 = cities.indexOf((max-5)+""); 16 long mid = System.nanoTime(); 17 System.out.println(mid - start); 18 //binarySearch查找到索引值 19 int index2 = Collections.binarySearch(cities, (max-5)+""); 20 long end = System.nanoTime(); 21 System.out.println(end - mid); 22 System.out.println("索引值(indexOf)："+index1); 23 System.out.println("索引值（binarySearch)："+index2); 24 } 25 }
运行输出:
16876685 408528 索引值(indexOf)：1199995 索引值（binarySearch)：-1201
这个地方binarySearch输出负值....我没有调查...如果把这个max改的小一点就没有任何问题.
两种方式的索引值都一样.
binarySearch()的索引效率比indexOf高很多...(具体还要看要查找的值在list中的前后位置)
本文转自SummerChill博客园博客，原文链接：http://www.cnblogs.com/DreamDrive/p/5660155.html，如需转载请自行联系原作者
