contains与binarySearch的性能比较
查找List中的元素有两种方法，一个是使用contains()方法，还有一个是使用Collectoins.binarySearch()。binarySearch()方法有两种实现，一个版本是接受List和Comparator对象作为参数，另一个是接受List以及Comparable对象。这个方法使用二分查找算法来查询指定列表中的某个元素。在调用这个方法前，列表中的元素得按照它们的自然顺序进行升序排列。如果列表没有排序的话，方法调用的结果是不确定的。如果列表有多个元素与查找的元素一样，那么返回的具体是哪一个是不确定的。对于一个可”随机访问“的列表来说，算法的时间复杂度是O(log(n)。如果指定的列表没有实现RandomAccess接口并且列表长度很大的话，这个方法会基于迭代器来进行二分法的查找，它会执行O(n)次链接的遍历以及O(log n)次元素的比较。在方法的结尾，如果查找到了该元素，则返回对应元素在列表中的序号，否则返回的是(-(插入点序号)-1)。插入点的意思是这个元素应该在这个列表中的这个位置进行插入：第一个大于该查找元素的值所在的位置，如果所有元素都小于它的话则是list.size()。这意味着，当且仅当元素查找成功时，返回值才会大于等于0。List接口常见的实现比如ArrayList, Vector, CopyOnWriteArrayList和Stack都实现了RandomAccess接口，它们可以用来进行二分查找，不过还有些别的实现比如LinkedList，它没有实现RandomAccess接口，因此不适合使用二分查找。由于二分查找只能在排好序的列表中进行，因为在查找前你得先对列表排序，这可能会影响到性能，尤其是你的列表很大并且本来就无序的情况下。
下面是一段使用二分法来查找对象的程序。我们有一个包含1百万个整数的列表，这里同时使用contains()及binarySearch()方法进行搜索。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
/** * Java program to perform binary search in Java collection e.g List, Set
* @author Javin Paul
*/
public class BinarySearchTest {
public static final Logger logger = LoggerFactory.getLogger(BinarySearchTest.class);
public static void main(String args[]) {
//creating List
List<Integer> numbers = new ArrayList<Integer>(1000000); //List of 1M records
//initializing List
for(int i =0; i<numbers.size(); i++){
numbers.add(new Integer(i));
}
//performing contains search
long startTime = System.nanoTime();
boolean isExist = numbers.contains(new Integer(1000000));
long totalTime = System.nanoTime() - startTime;
logger.info("Time to search 1Mth Record using contains() is {} nano seconds", totalTime);
//performing binary search
startTime = System.nanoTime();
Collections.sort(numbers); // List needs to be sorted for Binary Search
Integer number = Collections.binarySearch(numbers, new Integer(1000000));
totalTime = System.nanoTime() - startTime;
logger.info("Time to search 1Mth Record using binary search is {} nano seconds", totalTime);
}
}输出结果：
2013-06-04 23:23:17,834 0 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using contains() is 51404 nano seconds
2013-06-04 23:23:17,849 15 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using binary search is 554261 nano seconds从结果中可以看到，contains()方法比二分法要快了10倍，这说明使用contains()方法来搜索列表中的元素非常有效，尤其是当列表实现了RandomAccess接口的情况下。
译注：作者这么说似乎不太公平，如果列表原本就有序的话，二分查找还是相当快的，这里他是加上了排序的时间。如果排序后能进行重复利用，也还是比较划算的。
感谢网友风云无浪指出的问题，其实文中程序的列表是空的。不过修改完后该程序运行的结果仍然是相差大概10倍。当然了，这还是因为算上了排序的时间，毕竟单独从搜索的效率来说的话，二分法通常来说肯定是比顺序查找要快的。
原创文章转载请注明出处：contains与binarySearch的性能比较 英文原文链接
