Java Collections.binarySearch()方法及实例

java.util.Collections.binarySearch()方法是java.util.Collections类中的一个方法，用于返回一个对象在排序列表中的位置。

// Returns index of key in sorted list sorted in
// ascending order
public static int binarySearch(List slist, T key)

// Returns index of key in sorted list sorted in
// order defined by Comparator c.
public static int binarySearch(List slist, T key, Comparator c)

If key is not present, the it returns "(-(insertion point) - 1)". 
The insertion point is defined as the point at which the key 
would be inserted into the list.

如果列表中的元素不能用指定的比较器进行比较，或者搜索键不能与元素进行比较，该方法会抛出 ClassCastException 。

在一个按升序排序的列表中搜索一个int键：

// Java program to demonstrate working of Collections.
// binarySearch()
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class GFG {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);
  
        // 10 is present at index 3.
        int index = Collections.binarySearch(al, 10);
        System.out.println(index);
  
        // 13 is not present. 13 would have been inserted
        // at position 4. So the function returns (-4-1)
        // which is -5.
        index = Collections.binarySearch(al, 13);
        System.out.println(index);
    }
}

输出:

3
-5

在按降序排序的列表中搜索一个int键

// Java program to demonstrate working of Collections.
// binarySearch() in an array sorted in descending order.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class GFG {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(100);
        al.add(50);
        al.add(30);
        al.add(10);
        al.add(2);
  
        // The last parameter specifies the comparator
        // method used for sorting.
        int index = Collections.binarySearch(
            al, 50, Collections.reverseOrder());
  
        System.out.println("Found at index " + index);
    }
}

输出:

Found at index 1

在用户定义的类对象列表中进行搜索：

// Java program to demonstrate working of Collections.
// binarySearch() in a list of user defined objects
import java.util.*;
  
class Binarysearch {
    public static void main(String[] args)
    {
        // Create a list
        List<Domain> l = new ArrayList<Domain>();
        l.add(new Domain(10, "www.geeksforgeeks.org"));
        l.add(new Domain(20, "practice.geeksforgeeks.org"));
        l.add(new Domain(30, "code.geeksforgeeks.org"));
        l.add(new Domain(40, "www.geeksforgeeks.org"));
  
        Comparator<Domain> c = new Comparator<Domain>() {
            public int compare(Domain u1, Domain u2)
            {
                return u1.getId().compareTo(u2.getId());
            }
        };
  
        // Searching a domain with key value 10. To search
        // we create an object of domain with key 10.
        int index = Collections.binarySearch(
            l, new Domain(10, null), c);
        System.out.println("Found at index  " + index);
  
        // Searching an item with key 5
        index = Collections.binarySearch(
            l, new Domain(5, null), c);
        System.out.println(index);
    }
}
  
// A user-defined class to store domains with id and url
class Domain {
    private int id;
    private String url;
  
    // Constructor
    public Domain(int id, String url)
    {
        this.id = id;
        this.url = url;
    }
  
    public Integer getId() { return Integer.valueOf(id); }
}

输出:

0
-1

Arrays .binarysearch() vs Collections.binarySearch()

Arrays.binarysearch()适用于数组，也可以是原始数据类型。Collections .binarysearch() 适用于对象集合，如 ArrayList 和 LinkedList。

要点：

如果输入的列表没有被排序，结果是不确定的。
如果有重复的，不保证哪一个会被找到。
对于像ArrayList这样的 “随机访问 “列表，该方法运行时间为log(n)。如果指定的列表没有实现RandomAccess接口，而且规模较大，该方法将进行基于迭代器的二进制搜索，执行O(n)的链接遍历和O(log n)的元素比较。