Java List二分查找与contains性能对比

Java 提供了两个方法，即 Collections.binarySearch() 和 contains() 来寻找一个列表中的元素。在引擎盖下，contains()方法使用indexOf()方法来搜索元素。indexOf()方法在列表中线性循环，将每个元素与键进行比较，直到找到键为止，并返回真，否则当没有找到元素时返回假。Collections.binarySearch()的时间复杂度是O(log2(n))。但是如果我们想使用这个方法，那么列表应该是被排序的。如果列表没有被排序，那么我们需要在使用 Collections.binarySearch() 之前对其进行排序，这需要 O(nlog(n)) 的时间。

如何选择

如果要找的元素靠近列表的起始点，那么contains()方法的性能会更好，因为contains()从列表的起始点开始线性地搜索该元素。
如果元素被排序，并且元素的数量相对较大，那么 Collections.binarySearch() 就更快，因为它只需要 O(log2(n)) 的时间。
如果列表中的元素没有被排序，那么contains()方法的性能会更好，因为它只需要O(n)时间，但如果搜索查询的数量很高，那么Collections.binarySearch()方法的整体性能会更好，因为我们在第一次搜索时只对列表进行一次排序，需要O(nlog(n))时间，之后每次搜索操作需要O(log(n))时间。
对于一个包含相对较少元素的列表来说，contains()会产生更好的速度。
如果我们使用的LinkedList没有实现RandomAccess接口，因此无法提供O(1)时间来访问一个元素，那么我们应该选择contains()而不是Collections.binarySearch()，因为Collections.binary search()需要O(n)来进行链接遍历，然后需要O(log(n))时间来进行比较。

现在我们将讨论两种变体，即排序后的列表是

1.分类的小名单
2.分类的大名单
3.未分类列表

案例1：对于一个小型的排序列表

在下面提到的代码中，我们以一个只包含0到99的100个元素的排序列表为例，我们搜索了40个元素，正如我们在上面看到的，在小列表中，contains()在速度上比Collections.binarySearch有优势。

示例

// Java program to compare the performance
// of contains() and Collections.binarySearch()
// For a Small List (Case 1)
 
// Importing ArrayList and Collections classes
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating an object of ArrayList
        // Declaring object of integer type
        ArrayList<Integer> arr = new ArrayList<>();
 
        // Iterating over object using for loop
        for (int i = 0; i < 100; i++) {
            arr.add(i);
        }
 
        // Calculating and printing the time taken
        // where we are finding 40
        // Using contains() method
        long start = System.nanoTime();
        arr.contains(40);
        long end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time taken to find 40 inside arr using contains() = "
            + (end - start) + " nano seconds");
 
        // Calculating and printing the time taken
        // to find 40
        // Using Collections.binarySearch() method
        start = System.nanoTime();
        Collections.binarySearch(arr, 40);
        end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time taken to find 40 inside arr using binarySearch() = "
            + (end - start) + " nano seconds");
    }
}

输出

Time taken to find 40 inside arr using contains() = 16286 nano seconds
Time taken to find 40 inside arr using binarySearch() = 87957 nano seconds

案例2：对于一个大的排序的列表

在下面提到的例子中，我们创建了一个排序的ArrayList，其中包含100000个从0到99999的元素，我们使用contains()和Collections.sort()方法在其中找到40000个元素。由于该列表是排序的，并且有相对较多的元素，Collections.sort()的性能比contains()方法更好。

示例

// Java program to Find and Compare the Performance
// of contains() and Collections.sort() Methods
// For Large Sorted ArrayList (Case 2)
 
// Importing ArrayList and Collections classes
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
 
// Main class
public class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating an object of ArrayList class
        // Declaring object of Integer type
        ArrayList<Integer> arr = new ArrayList<>();
 
        // Iterating over the object
        for (int i = 0; i < 100000; i++) {
 
            // Adding elements using add() method
            arr.add(i);
        }
 
        // Calculating and printing the time taken
        // to find 40000 using contains()
        long start = System.nanoTime();
        arr.contains(40000);
        long end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time taken to find 40000 inside arr "
            + "using contains() = " + (end - start)
            + " nano seconds");
 
        // Calculating and printing the time taken
        // to find 40000 using Collections.binarySearch()
        start = System.nanoTime();
        Collections.binarySearch(arr, 40000);
        end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time taken to find 40000 inside arr "
            + "using binarySearch() = " + (end - start)
            + " nano seconds");
    }
}

输出

Time taken to find 40000 inside arr using contains() = 6651276 nano seconds
Time taken to find 40000 inside arr using binarySearch() = 85231 nano seconds

案例3：对于一个未排序的列表

在下面提到的代码中，我们创建了一个未排序的ArrayList，在其中存储了0到100000之间的随机数字。由于该列表是未排序的，所以contains()方法的性能更好，因为它只需要O(n)时间，而使用Collections.sort()方法我们首先要对列表进行排序，这需要额外的O(nlog(n))时间，然后需要O(log2(n))时间来搜索该元素。

示例

// Java program to compare the performance
// of contains() and Collections.sort() method
//  on an unsorted ArrayList (Case3)
 
// Importing ArrayList and Collections class
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating an object of ArrayList class
        ArrayList<Integer> arr = new ArrayList<>();
 
        // Iterating between 0 to 100000 numbers
        for (int i = 0; i < 100000; i++) {
 
            // Generating random numbers as iterated
            // using random() function
            int rand = (int)(Math.random() * 100000);
 
            // Later storing them inside our list
            arr.add(rand);
        }
 
        // Setting the key to be found as the element
        // at index 30000 inside of unsorted list
        int key = arr.get(30000);
 
        // Calculating and printing the time taken
        // to find the key using contains()
        long start = System.nanoTime();
        arr.contains(key);
        long end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time takes to find " + key
            + " inside arr using contains() = "
            + (end - start) + " nano seconds");
 
        // Calculating and printing the time taken to
        // find the key using Collections.binarySearch()
        // after sorting the list using Collections.sort()
        // method
        start = System.nanoTime();
        Collections.sort(arr);
        Collections.binarySearch(arr, key);
        end = System.nanoTime();
 
        // Print statement
        System.out.println(
            "Time takes to find " + key
            + " inside arr using binarySearch() = "
            + (end - start) + " nano seconds");
    }
}

输出

Time takes to find 66181 inside arr using contains() = 8331486 nano seconds
Time takes to find 66181 inside arr using binarySearch() = 140322701 nano seconds