Java中的Collections.binarySearch()及其示例

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

// 返回按升序排序的已排序列表sorted中key的索引
public static int binarySearch(List slist, T key)

// 返回按Comparator c所定义的顺序排序的已排序列表sorted中key的索引
public static int binarySearch(List slist, T key, Comparator c)

如果key不存在，则返回“(-(插入点) – 1)”。插入点被定义为将键插入列表中的位置。

如果列表的元素使用指定的比较器不能进行比较，或者搜索键与元素不可比较，则该方法会抛出 ClassCastException 异常。
在升序排序的列表中搜索int键：

// Java演示Collections.binarySearch()的工作。
// 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在索引3处
        int index = Collections.binarySearch(al, 10);
        System.out.println(index);

        // 13不在列表中。13会被插入到位置4。
        // 所以函数返回(-4-1)，即-5。
        index = Collections.binarySearch(al, 13);
        System.out.println(index);
    }
}

输出

3
-5

在降序排序的列表中搜索int键。

// Java演示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(100);
        al.add(50);
        al.add(30);
        al.add(10);
        al.add(2);

        // 最后一个参数指定用于排序的比较器方法。
        int index = Collections.binarySearch(
            al, 50, Collections.reverseOrder());

        System.out.println("Found at index " + index);
    }
}

输出

Found at index 1

在自定义类对象的列表中搜索：

// Java程序以示Collections的工作原理。
//在一个用户定义对象的列表中进行二分查找
import java.util.*;

class Binarysearch {
    public static void main(String[] args)
    {
        //创建一个列表
        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());
            }
        };

        //使用key value 10搜索一个域名。为了搜索，我们要创建一个具有key 10的domain对象。
        int index = Collections.binarySearch(
            l, new Domain(10, null), c);
        System.out.println("Found at index  " + index);

        //使用key 5搜索一个域名
        index = Collections.binarySearch(
            l, new Domain(5, null), c);
        System.out.println(index);
    }
}

//一个用户定义的类，用于存储具有id和url的域名
class Domain {
    private int id;
    private String url;

    //构造函数
    public Domain(int id, String url)
    {
        this.id = id;
        this.url = url;
    }

    public Integer getId() { return Integer.valueOf(id); }
}

输出

Found at index  0
-1

复杂度分析:

时间复杂度:

在Collections类中二分查找(binarySearch())方法的时间复杂度为O(log n)，其中n是列表的大小。

辅助空间:

在Collections类中二分查找(binarySearch())方法的空间复杂度为O(1)，因为它不需要创建任何其他的数据结构。

数组 .binarysearch() vs Collections.binarySearch()

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

要点：

如果输入的列表未排序，则结果是未定义的。
如果有重复的元素，则没有保证哪一个会被找到。
此方法对于“随机访问”列表（如ArrayList）的运行时间为log(n)。如果指定的列表没有实现RandomAccess接口并且很大，则此方法将执行一个基于迭代器的二分搜索，它执行O(n)的链接遍历和O(log n)的元素比较。

参考：

https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T)