如何检查一个数组（未排序）中是否包含某个特定的值？在Java中，这是一个非常有用并又很常用的操作。同时，在StackOverflow中，有时一个得票非常高的问题。在得票比较高的几个回答中，时间复杂度差别也很大。在下面的例子中，D瓜哥将展示每个方法花费的时间。
1、不同的实现方式
1) 使用List：
1/**
2 * Coder：D瓜哥，
http://www.diguage.com/3 */
4
5public static boolean useList(String[] arr, String targetValue) {
6 return Arrays.asList(arr).contains(targetValue);
7}
2) 使用Set：
1/**
2 * Coder：D瓜哥，
http://www.diguage.com/3 */
4
5public static boolean useSet(String[] arr, String targetValue) {
6 Set<String> set = new HashSet<String>(Arrays.asList(arr));
7 return set.contains(targetValue);
8}
3) 使用循环：
01/**
02 * Coder：D瓜哥，
http://www.diguage.com/03 */
04
05public static boolean useLoop(String[] arr, String targetValue) {
06 for (String s : arr) {
07 if (s.equals(targetValue)) {
08 return true;
09 }
10 }
11 return false;
12}
4) 使用Arrays.binarySearch：
下面的代码是错误。但是，为了这个回答的完整性，还是将其列在这里。binarySearch()方法仅能用于已排序的数组。不过，你将会被下面的结果所震惊。
01/**
02 * Coder：D瓜哥，
http://www.diguage.com/03 */
04
05public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
06 int a = Arrays.binarySearch(arr, targetValue);
07 if (a > 0) {
08 return true;
09 } else {
10 return false;
11 }
12}
2、时间复杂度
使用如下代码来粗略比较不同实现间的时间复杂度。虽然不是很精确，但是思路确实正确的。我们将看看数组在有5、1k、10k个元素的情况下的不同表现。
01/**
02 * Coder：D瓜哥，
http://www.diguage.com/03 */
04
05public static void main(String[] args) {
06 String[] arr = new String[]{"CD", "BC", "EF", "DE", "AB"};
07
08 // use list
09 long startTime = System.nanoTime();
10 for (int i = 0; i < 100000; i++) {
11 useList(arr, "A");
12 }
13 long endTime = System.nanoTime();
14 long duration = endTime - startTime;
15 System.out.println("useList: " + duration / 1000000);
16
17 // use set
18 startTime = System.nanoTime();
19 for (int i = 0; i < 100000; i++) {
20 useSet(arr, "A");
21 }
22 endTime = System.nanoTime();
23 duration = endTime - startTime;
24 System.out.println("useSet: " + duration / 1000000);
25
26 // use loop
27 startTime = System.nanoTime();
28 for (int i = 0; i < 100000; i++) {
29 useLoop(arr, "A");
30 }
31 endTime = System.nanoTime();
32 duration = endTime - startTime;
33 System.out.println("useLoop: " + duration / 1000000);
34
35 // use Arrays . binarySearch ()
36 startTime = System.nanoTime();
37 for (int i = 0; i < 100000; i++) {
38 useArraysBinarySearch(arr, "A");
39 }
40 endTime = System.nanoTime();
41 duration = endTime - startTime;
42 System.out.println("useArrayBinary: " + duration / 1000000);
43}
结果：
1useList: 12
2useSet: 65
3useLoop: 2
4useArrayBinary: 7
使用大一点的数组（1k个元素）：
01/**
02 * Coder：D瓜哥，
http://www.diguage.com/03 */
04
05int length = 1000;
06String[] arr = new String[length];
07
08Random s = new Random();
09for (int i = 0; i < length; i++) {
10 arr[i] = String.valueOf(s.nextInt());
11}
结果：
1useList: 115
2useSet: 2010
3useLoop: 97
4useArrayBinary: 9
使用更大一点的元素（10k个元素）：
01/**
02 * Coder：D瓜哥，
http://www.diguage.com/03 */
04
05int length = 10000;
06String[] arr = new String[length];
07
08Random s = new Random();
09for (int i = 0; i < length; i++) {
10 arr[i] = String.valueOf(s.nextInt());
11}
结果：
1useList: 1678
2useSet: 25609
3useLoop: 1802
4useArrayBinary: 10
D瓜哥注：
以下内容是安装原文翻译过来的。但是，从上面的结果来看，实际的表现和文章内容不太一样，D瓜哥自己的推断和文章介绍的是一样的。但是，实际测试的结果却截然不同。但是，至于为什么会出现这种问题，还需要进一步研究。
从上面的结果可以清晰看到，使用简单循环的相比使用其他集合操作更高效。很多很多开发人员使用第一种方法，但是它并不是最高效的。将数组转化成其他的任何集合类型都需要先将所有元素读取到集合类中，才能对这个集合类型做其他的事情。
当使用Arrays.binarySearch()方法时，数组必须是排好序的。如果数组不是排好序的，则不能使用这个方法。
事实上，如果你真的需要高效地检查一个数组或者集合中是否包含一个值，一个排好序的数组或者树可以达到O(log(n))的时间复杂度，HashSet甚至能达到O(1)的时间复杂度。
《Simple Java》是一本讲解Java面试题的书。讲解也有不少独特之处，为了面试，《简易Java》走起！
作 者：
D瓜哥，http://www.diguage.com/原文链接：
http://www.diguage.com/archives/112.html版权声明：非特殊声明均为本站原创作品，转载时请注明作者和原文链接。
0您可能喜欢：
简易Java（18）：属性能否重写？为什么？ 简易Java（17）：Java中的实例初始化器是什么？ 简易Java（08）：为什么Java中的字符串是不可变的？ Java7并发示例集110：线程组 Java7并发示例集106：等待线程执行终止无觅关联推荐[?]如果感觉这篇文章不错，请点击这里的分享按钮，分享到微博等地方去，让更多人受益！
您的支持是D瓜哥最大的写作动力！谢谢！
