高效判断数组中是否包含某个特定的值

矫情吗；* 2022-05-21 00:45 279阅读 0赞

# 4 种方式 #

## 使用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 ##

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

# 结论： #

从测试结果可以看出，使用简单的循环语句比使用任何集合都高效，很大一部分开发人员选择使用第一种方法（List），但这种方法其实是相对低效的。在使用集合提供的API前，需要把一个数组放到集合里，这需要消耗一定的时间，特别是对于Set集合；（注：其实ArrayList集合的性能跟普通的循环语句差不多，因为对于ArrayList，转换成集合的时候，仅仅是改变了内部的数组索引，遍历判断的时候，跟普通的循环语句类似）；

如果要使用Arrays.binarySearch()方法，前提是数组要有序，在这个测试demo中，很显然数组是无序的，因此不该被使用；

事实上，如果你确实需要高效的去检查数组或集合中是否包含某个值，一个有序列表或者有序树能把时间复杂度降低到O(log(n))，或者使用散列集合，时间复杂度为O(1)；

转载自：[https://blog.csdn.net/sinat\_33536912/article/details/52093989][https_blog.csdn.net_sinat_33536912_article_details_52093989]

[https_blog.csdn.net_sinat_33536912_article_details_52093989]: https://blog.csdn.net/sinat_33536912/article/details/52093989