程序喵
怎样判断一个无序数组是否包含某个特定值？这在JAVA中是一个非常实用的操作，在Stack Overflow问答网站中也同样是一个热门问题；
要完成这个判断，可以通过若干种不同的方式实现，每种实现方式对应的时间复杂读会有很大的不同；
接下来我将展示不同实现方式的时间开销。
四种不同方式检查数组是否包含某个值
使用List：
public static boolean useList(String[] arr, String targetValue) {
return Arrays.asList(arr).contains(targetValue);
}使用Set：
public static boolean useSet(String[] arr, String targetValue) {
Set<String> set = new HashSet<String>(Arrays.asList(arr));
return set.contains(targetValue);
}使用简单的循环语句：
public static boolean useLoop(String[] arr, String targetValue) {
for (String s : arr) {
if (s.equals(targetValue))
return true;
}
return false;
}使用Arrays.binarySearch()方法：
下面的代码是错误的，之所以列在下面是出于完整性考虑（四种判断方式），binarySearch()二分查找只能用于有序数组。
运行下面程序，你有可能会得到异常结果；
public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
int a = Arrays.binarySearch(arr, targetValue);
if (a > 0)
return true;
else
return false;
}四种实现方式对应的时间开销
以下代码可计算出以上四种实现方式大致的时间消耗，基本策略是使用不同大小的数组（5,1k，10k）做测试，可能不是很精准，但这种方式很简单；
数组大小为5：
public static void main(String[] args) {
String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB" };
// use list
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useList(arr, "A");
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("useList: " + duration / 1000000);
// use set
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useSet(arr, "A");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useSet: " + duration / 1000000);
// use loop
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useLoop(arr, "A");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useLoop: " + duration / 1000000);
// use Arrays.binarySearch()
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useArraysBinarySearch(arr, "A");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useArrayBinary: " + duration / 1000000);
}
运行结果：
useList: 13
useSet: 72
useLoop: 5
useArraysBinarySearch: 9数组大小为1000：
String[] arr = new String[1000];
Random s = new Random();
for (int i = 0; i < 1000; i++) {
arr[i] = String.valueOf(s.nextInt());
}
运行结果：
useList: 112
useSet: 2055
useLoop: 99
useArrayBinary: 12数组大小为10000：
String[] arr = new String[10000];
Random s = new Random();
for (int i = 0; i < 10000; i++) {
arr[i] = String.valueOf(s.nextInt());
}
运行结果：
useList: 1590
useSet: 23819
useLoop: 1526
useArrayBinary: 12结论
从测试结果可以看出，使用简单的循环语句比使用任何集合都高效，很大一部分开发人员选择使用第一种方法（List），但这种方法其实是相对低效的。在使用集合提供的API前，需要把一个数组放到集合里，这需要消耗一定的时间，特别是对于Set集合；（注：其实ArrayList集合的性能跟普通的循环语句差不多，因为对于ArrayList，转换成集合的时候，仅仅是改变了内部的数组索引，遍历判断的时候，跟普通的循环语句类似）；
如果要使用Arrays.binarySearch()方法，前提是数组要有序，在这个测试demo中，很显然数组是无序的，因此不该被使用；
事实上，如果你确实需要高效的去检查数组或集合中是否包含某个值，一个有序列表或者有序树能把时间复杂度降低到O(log(n))，或者使用散列集合，时间复杂度为O(1)；
译文链接：http://www.programcreek.com/2014/04/check-if-array-contains-a-value-java/
未经允许请勿转载：程序喵 » 怎样高效判断数组中是否包含某个特定值