灵魂拷问：如何检查Java数组中是否包含某个值 ？ (2)

由于我们不确定数组是否已经排序过，所以我们先来比较一下前三种方法的时间复杂度。由于调用 1 次的时间太短，没有统计意义，我们就模拟调用 100000 次，具体的测试代码如下所示。

String[] arr = new String[]{"沉", "默", "王", "二", "真牛逼"};
// 使用 List
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    useList(arr, "真牛逼");
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("useList:  " + duration / 1000000);

// 使用 Set
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    useSet(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useSet:  " + duration / 1000000);

// 使用一个简单的循环
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    useLoop(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useLoop:  " + duration / 1000000);

PS：nanoTime() 获取的是纳秒级，这样计算的时间就更精确，最后除以 1000000 就是毫秒。换算单位是这样的：1秒=1000毫秒，1毫秒=1000微秒，1微秒=1000纳秒。

统计结果如下所示：

useList:  6
useSet:  40
useLoop:  2

假如把数组的长度增加到 1000，我们再来看一下统计结果。

String[] arr = new String[1000];

Random s = new Random();
for(int i=0; i< 1000; i++){
    arr[i] = String.valueOf(s.nextInt());
}

这时数组中是没有我们要找的元素的。为了做比较，我们顺便把二分查找也添加到统计项目中。

// 使用二分查找
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    useArraysBinarySearch(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useArraysBinarySearch:  " + duration / 1000000);

统计结果如下所示：

useList:  91
useSet:  1460
useLoop:  70
useArraysBinarySearch:  4

我们再把数组的长度调整到 10000。

String[] arr = new String[10000];

Random s = new Random();
for(int i=0; i< 10000; i++){
    arr[i] = String.valueOf(s.nextInt());
}

统计结果如下所示：

useList:  1137
useSet:  15711
useLoop:  1115
useArraysBinarySearch:  5

从上述的统计结果中可以很明显地得出这样一个结论：使用简单的 for 循环，效率要比使用 List 和 Set 高。这是因为把元素从数组中读出来再添加到集合中，就要花费一定的时间，而简单的 for 循环则省去了这部分时间。

在得出这个结论之前，说实话，我最喜欢的方式其实是第一种“使用 List”，因为只需要一行代码 Arrays.asList(arr).contains(targetValue) 就可以搞定。

虽然二分查找（Arrays.binarySearch()）花费的时间明显要少得多，但这个结论是不可信的。因为二分查找明确要求数组是排序过的，否则查找出的结果是没有意义的。可以看一下官方的 Javadoc。

Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object []) method) prior to making this call. If it is not sorted, the results are undefined.

实际上，如果要在一个数组或者集合中有效地确定某个值是否存在，一个排序过的 List 的算法复杂度为 O(logn)，而 HashSet 则为 O(1)。

我们再来发散一下思维：怎么理解 O(logn) 和 O(1) 呢？