1700444670
1700444671
cities.add(“上海”);
1700444672
1700444673
cities.add(“广州”);
1700444674
1700444675
cities.add(“广州”);
1700444676
1700444677
cities.add(“北京”);
1700444678
1700444679
cities.add(“天津”);
1700444680
1700444681
//indexOf方法取得索引值
1700444682
1700444683
int index1=cities.indexOf(“广州”);
1700444684
1700444685
//binarySearch查找到索引值
1700444686
1700444687
int index2=Collections.binarySearch(cities,“广州”);
1700444688
1700444689
System.out.println(“索引值(indexOf):”+index1);
1700444690
1700444691
System.out.println(“索引值(binarySearch):”+index2);
1700444692
1700444693
}
1700444694
1700444695
先不考虑运行结果,直接看JDK上对binarySearch的描述:使用二分搜索法搜索指定列表,以获得指定对象。其实现的功能与indexOf是相同的,只是使用的是二分法搜索列表,所以估计两种方法返回结果是一样的,看结果:
1700444696
1700444697
索引值(indexOf):1
1700444698
1700444699
索引值(binarySearch):2
1700444700
1700444701
结果不一样,虽然说我们有两个“广州”这样的元素,但是返回的结果都应该是1才对呀,为何binarySearch返回的结果是2呢?问题就出在二分法搜索上,二分法搜索就是“折半折半再折半”的搜索方法,简单,而且效率高。看看JDK是如何实现的。
1700444702
1700444703
public static<T>int binarySearch(List<?extends Comparable<?super T>>list, T key){
1700444704
1700444705
if(list instanceof RandomAccess||list.size()<5000)
1700444706
1700444707
//随机存取列表或者元素数量少于5000的顺序存取列表
1700444708
1700444709
return Collections.indexedBinarySearch(list, key);
1700444710
1700444711
else
1700444712
1700444713
//元素数量大于5000的顺序存取列表
1700444714
1700444715
return Collections.iteratorBinarySearch(list, key);
1700444716
1700444717
}
1700444718
1700444719
ArrayList实现了RandomAccess接口,是一个顺序存取列表,使用了indexdBinarySearch方法,代码如下:
[
上一页 ]
[ :1.70044467e+09 ]
[
下一页 ]