数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Java 列表中二分查找与 Contains 方法的性能比较
在集合中搜索元素时，Java 根据您使用的数据结构提供了不同的选项。在列表中搜索的两种常用方法是二分查找和contains()方法。在这篇博文中，我们将比较 Java 列表中二分查找和 contains 方法的性能，重点介绍它们的差异、优势和最佳用例。
二分查找
二分查找是在已排序列表中查找特定成员的有效方法。它采用分治法，不断将搜索空间减半，直到找到目标元素或搜索空间耗尽。二分查找假设列表已排序，并将目标元素与当前搜索区域的中间元素进行比较，以确定是移动到搜索区域的左半部分还是右半部分。
该算法的时间复杂度为 O(log n)，其中 n 是列表中元素的数量。对于大型排序列表，二分查找非常高效，因为它在每次迭代中都消除了剩余搜索空间的一半，从而减少了比较次数。
contains() 方法
contains() 方法是一种快速确定列表是否包含特定成员的方法。它迭代列表中的每个元素，并将其与目标元素进行比较，直到找到匹配项或到达列表的末尾。contains 方法的时间复杂度为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) {
// 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 方法比较元素，在某些情况下可能更容易使用。
用例
总而言之，以下是二分查找和 contains 的推荐用例：
当需要高效查找元素时，二分查找最适合大型排序列表。当列表相对静态或排序开销可以接受时，它特别有用。
contains 适用于较小的未排序列表或列表经常修改且排序开销令人担忧的情况。当不需要对列表进行排序时，它是一种简单方便的搜索方法。
结论
总之，二分查找和 contains 是在 Java 列表中搜索元素的两种不同方法。二分查找对于大型排序列表非常高效，而 contains 更适合较小的未排序列表或排序开销令人担忧的情况。选择合适的方法取决于列表的特性和应用程序的具体要求。
439 次浏览
