二分查找与Java列表中的contains()方法性能对比

在搜索集合中的元素时，根据使用的数据结构，Java提供了不同的选项。在列表中搜索的两种流行方法是二分查找和 contains() 方法。在本博客文章中，我们将比较二分查找和contains方法在Java列表中的性能，突出它们的差异、优势和最佳用例。

二分查找

二分查找是一种在有序列表中定位特定成员的高效方法。搜索空间定期一分为二，直到找到目标元素或搜索空间在分治方法中耗尽。二分查找假定列表已经被排序，并将目标元素与当前搜索区域的中心元素进行比较，以确定是继续移到搜索区域的左半部分还是右半部分。

该算法的时间复杂度为O(log n)，其中n是列表中的元素数量。二分查找对于大型排序列表非常高效，因为在每次迭代中它消除了剩余搜索空间的一半，从而减少了比较的次数。

contains()方法

contains()方法 是一种快速确定列表是否包含特定成员的方法。在找到匹配项或达到列表末尾之前，它会重复遍历列表中的每个元素，并将其与目标元素进行比较。includes方法的时间复杂度为O(n)，其中n是列表中的条目数，它不要求列表排序。这意味着随着列表大小的增加，找到一个元素所需的时间会线性增加。

示例

以下是一个程序，用于比较在包含元素从0到149的已排序列表中查找数字60时，contains方法和二分查找之间的性能时间：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HelloWorld {

    public static void main(String[] args) {
        // Creating a sorted list of integers from 0 to 99
        List<Integer> sortedList = new ArrayList<>();
        for (int i = 0; i < 150; i++) {
            sortedList.add(i);
        }

        // Searching for number 40 using binary search
        long startTimeBinarySearch = System.nanoTime();
        int indexBinarySearch = Collections.binarySearch(sortedList, 60);
        long endTimeBinarySearch = System.nanoTime();
        long executionTimeBinarySearch = endTimeBinarySearch - startTimeBinarySearch;

        System.out.println("Binary Search Result: Index " + indexBinarySearch);
        System.out.println("Binary Search Execution Time: " + executionTimeBinarySearch + " nanoseconds");

        // Searching for number 40 using contains
        long startTimeContains = System.nanoTime();
        boolean foundContains = sortedList.contains(40);
        long endTimeContains = System.nanoTime();
        long executionTimeContains = endTimeContains - startTimeContains;

        System.out.println("Contains Result: " + foundContains);
        System.out.println("Contains Execution Time: " + executionTimeContains + " nanoseconds");
    }
}

输出

Binary Search Result: Index 60
Binary Search Execution Time: 23805 nanoseconds
Contains Result: true
Contains Execution Time: 12073 nanoseconds

示例

以下是创建一个包含0到100,000之间随机数的未排序ArrayList的代码。我们将比较以下性能：

未排序时使用 contains() 方法。
排序列表后使用 Collections.binarySearch() 方法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class HelloWorld {
    public static void main(String[] args) {
        // Create an unsorted list of random numbers
        List<Integer> unsortedList = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            unsortedList.add(random.nextInt(100001));
        }
        // Searching for number 50000 using contains without sorting
        long startTimeContains = System.nanoTime();
        boolean foundContains = unsortedList.contains(50000);
        long endTimeContains = System.nanoTime();
        long executionTimeContains = endTimeContains - startTimeContains;

        System.out.println("Contains Result (Unsorted List): " + foundContains);
        System.out.println("Contains Execution Time (Unsorted List): " + executionTimeContains + " nanoseconds");

        // Sorting the list
        Collections.sort(unsortedList);

        // Searching for number 50000 using binary search after sorting
        long startTimeBinarySearch = System.nanoTime();
        int indexBinarySearch = Collections.binarySearch(unsortedList, 50000);
        long endTimeBinarySearch = System.nanoTime();
        long executionTimeBinarySearch = endTimeBinarySearch - startTimeBinarySearch;

        System.out.println("Binary Search Result (Sorted List): Index " + indexBinarySearch);
        System.out.println("Binary Search Execution Time (Sorted List): " + executionTimeBinarySearch + " nanoseconds");
    }
}

输出

Contains Result (Unsorted List): true
Contains Execution Time (Unsorted List): 2092909 nanoseconds
Binary Search Result (Sorted List): Index 499734
Binary Search Execution Time (Sorted List): 22943 nanoseconds

性能比较

二分搜索和contains()方法的性能取决于列表的特性和具体的使用情况。当在这两种方法之间选择时，请考虑以下几个因素：

列表大小： 二分搜索在大型排序列表上表现最佳，而contains()方法对于较小的未排序列表效果更好。随着列表的大小增加，由于其对数时间复杂度，二分搜索的优势变得更加明显。
排序开销： 二分搜索需要在初始或每次修改后对列表进行排序，这会导致额外的开销。如果列表经常被修改且排序开销较大，则使用contains方法可能更高效。
内存开销： 二分搜索在原始列表上操作，而无需创建任何额外的数据结构。相反，contains创建一个迭代器并在内部使用该列表的迭代器，这会引入一些内存开销。
元素相等性： 二分搜索依赖于使用Comparable或Comparator接口比较元素。如果元素类型未实现这些接口，则必须提供自定义比较器。另一方面，contains使用equals方法比较元素，在某些情况下可能更加直观易用。