資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
