二分搜索与 Java 列表中的包含性能

javaobject oriented programmingprogramming更新于 2024/8/16 0:12:17

在搜索集合中的元素时,Java 根据您使用的数据结构提供不同的选项。在列表中搜索的两种常用方法是二分搜索和 contains() 方法。在这篇博文中,我们将比较 Java 列表中二分搜索和包含的性能,重点介绍它们的区别、优势和最佳用例。

二分搜索

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

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

contains() 方法

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

示例

以下程序比较了 contains 方法和二分搜索在包含 0 到 149 的 100 个元素的排序列表中查找数字 60 的性能时间:

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

public class HelloWorld {

    public static void main(String[] args) {
        // 创建一个从 0 到 99 的整数排序列表
        List<Integer> sortedList = new ArrayList<>();
        for (int i = 0; i < 150; i++) {
        sortedList.add(i);
        }
        
        // 使用二分查找法搜索数字 40
        long startTimeBinarySearch = System.nanoTime();
        int indexBinarySearch = Collections.binarySearch(sortedList, 60);
        long endTimeBinarySearch = System.nanoTime();
        long executiveTimeBinarySearch = endTimeBinarySearch - startTimeBinarySearch;
        
        System.out.println("Binary Search Result: Index " + indexBinarySearch);
        System.out.println("Binary Search Execution Time: " + executionTimeBinarySearch + " nanoseconds");
        
        // 使用 contains 搜索数字 40
        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

示例

以下是创建未排序的 ArrayList 的代码,其中包含 0 到 100,000 之间的随机数。我们将比较 –

  • 未排序的 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) {
        // 创建一个未排序的随机数列表
        List<Integer> unsortedList = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
        unsortedList.add(random.nextInt(100001));
        }
        // 使用包含搜索数字 50000,无需排序
        long startTimeContains = System.nanoTime();
        boolean foundContains = unsortedList.contains(50000);
        long endTimeContains = System.nanoTime();
        long implementationTimeContains = endTimeContains - startTimeContains;
        
        System.out.println("Contains Result (Unsorted List): " + foundContains);
        System.out.println("Contains Execution Time (Unsorted List): " + executionTimeContains + " nanoseconds");
        
        // 对列表进行排序
        Collections.sort(unsortedList);
        
        // 排序后使用二分查找法搜索数字 50000
        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 方法来比较元素,在某些情况下使用这种方法可能更简单。

用例

总结一下,以下是二分查找和 contains 的推荐用例:

  • 当您需要高效地查找元素时,二分查找最适合大型排序列表。当列表相对静态或排序开销可接受时,它特别有用。

  • Contains 适用于较小的未排序列表或列表经常被修改且排序开销令人担忧的情况。当列表不需要排序时,这是一种简单方便的搜索方法。

结论

总之,二分搜索和包含是两种不同的在 Java 列表中搜索元素的方法。二分搜索对于大型排序列表非常有效,而包含更适合较小的未排序列表或当排序开销是一个问题时。选择正确的方法取决于列表的特征和应用程序的特定要求。


相关文章


有用资源