indexOf和binarySearch的对比

原创
2017/03/18 08:16
阅读数 174

在对一个列表进行检索的时候,我们经常使用的是indexOf方法进行检索,而Collections工具类也提供了一个检索的方法binarySearch,是使用二分搜索法搜索指定的列表。今天我们就来对比下这两个检索方式。

indexOf和binarySearch的对比

测试的程序

在程序中,我们定义了一个往list里面添加五个元素,然后分别使用binarySearch和indexOf方法进行检索,大家觉得返回的结果会是什么呢?

indexOf和binarySearch的对比

可以看到indexOf返回的是第一个元素出现的下标值没错,但是看到binarySearch检索的值已经出现了乱七八糟的情况,跟要求检索的结果不一样,那么这是为什么呢?我们来看下API对这个方法的说明。

indexOf和binarySearch的对比

binarySearch的API说明

可以看到这边已经说明了在调用之前必须根据列表元素的自然顺序对列表进行升序排序。二分搜索法就是“折半折半再折半”的搜索方法,如果没有排序,那么就无法确定是在小区(比中间值小的区域)查找还是在大区(比中间值大的区域)中查找。那么问题清楚了,也就可以有解决方案了,使用Collections.sort排下序就可以解决问题了。

indexOf和binarySearch的对比

排序后的结果

所以总结来说indexOf使用起来没什么限制,如果用binarySearch的话需要对列表先进行排序(当然排序完也有个缺陷,为了查找元素对列表进行排序,改变了其他元素在列表的位置,在业务处理的是就比较容易出错。也可以使用拷贝成一个数组,再排序查找,不要去把原表排序,就不会影响了)。indexOf是采用遍历去查找的,binarySearch是使用二分法查找,在性能方面来说,特别是在数据量很大的时候,binarySearch是占优的。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部