"地瓜哥"博客网

如何检查一个数组（未排序）中是否包含某个特定的值？在Java中，这是一个非常有用并又很常用的操作。同时，在StackOverflow中，有时一个得票非常高的问题。在得票比较高的几个回答中，时间复杂度差别也很大。在下面的例子中，D瓜哥将展示每个方法花费的时间。

1、不同的实现方式

1) 使用List：

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

public static boolean useList(String[] arr, String targetValue) {
    return Arrays.asList(arr).contains(targetValue);
}

2) 使用Set：

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

public static boolean useSet(String[] arr, String targetValue) {
    Set<String> set = new HashSet<String>(Arrays.asList(arr));
    return set.contains(targetValue);
}

3) 使用循环：

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

public static boolean useLoop(String[] arr, String targetValue) {
    for (String s : arr) {
        if (s.equals(targetValue)) {
            return true;
        }
    }
    return false;
}

4) 使用Arrays.binarySearch：

下面的代码是错误。但是，为了这个回答的完整性，还是将其列在这里。binarySearch()方法仅能用于已排序的数组。不过，你将会被下面的结果所震惊。

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
    int a = Arrays.binarySearch(arr, targetValue);
    if (a > 0) {
        return true;
    } else {
        return false;
    }
}

2、时间复杂度

使用如下代码来粗略比较不同实现间的时间复杂度。虽然不是很精确，但是思路确实正确的。我们将看看数组在有5、1k、10k个元素的情况下的不同表现。

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

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:  12
useSet:  65
useLoop:  2
useArrayBinary:  7

使用大一点的数组（1k个元素）：

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

int length = 1000;
String[] arr = new String[length];

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

结果：

useList:  115
useSet:  2010
useLoop:  97
useArrayBinary:  9

使用更大一点的元素（10k个元素）：

/**
 * Coder：D瓜哥，http://www.diguage.com/
 */

int length = 10000;
String[] arr = new String[length];

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

结果：

useList:  1678
useSet:  25609
useLoop:  1802
useArrayBinary:  10

D瓜哥注：

以下内容是安装原文翻译过来的。但是，从上面的结果来看，实际的表现和文章内容不太一样，D瓜哥自己的推断和文章介绍的是一样的。但是，实际测试的结果却截然不同。但是，至于为什么会出现这种问题，还需要进一步研究。

从上面的结果可以清晰看到，使用简单循环的相比使用其他集合操作更高效。很多很多开发人员使用第一种方法，但是它并不是最高效的。将数组转化成其他的任何集合类型都需要先将所有元素读取到集合类中，才能对这个集合类型做其他的事情。

当使用Arrays.binarySearch()方法时，数组必须是排好序的。如果数组不是排好序的，则不能使用这个方法。

事实上，如果你真的需要高效地检查一个数组或者集合中是否包含一个值，一个排好序的数组或者树可以达到O(log(n))的时间复杂度，HashSet甚至能达到O(1)的时间复杂度。

《Simple Java》是一本讲解Java面试题的书。讲解也有不少独特之处，为了面试，《简易Java》走起！