Java集合binarySearch使用教程

积累知识，胜过积蓄金银！毕竟在文章开发的过程中，会遇到各种各样的问题，往往都是一些细节知识点还没有掌握好而导致的，因此基础知识点的积累是很重要的。下面本文《Java Collections.binarySearch用法详解》，就带大家讲解一下知识点，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

Collections.binarySearch()用于在排序列表中高效查找目标值，时间复杂度为O(log n)，使用前必须确保列表已排序，否则结果不可预测；该方法有两个重载版本，分别适用于实现Comparable接口的元素和自定义Comparator比较规则的情况，查找成功返回索引，失败返回-(插入点)-1，可用于优化大型有序数据的搜索性能。

二分查找，简单来说，就是在排序好的列表中快速找到目标值的位置。Java 的 Collections.binarySearch() 方法就是干这个的。它比你自己手写二分查找要方便，而且经过了优化，效率更高。

Collections.binarySearch() 方法的使用其实挺直接的，但有些细节要注意，不然可能会踩坑。

如何正确使用 Collections.binarySearch()

Collections.binarySearch() 有两个主要的重载方法：

1. binarySearch(List> list, T key)：这个方法用于查找实现了 Comparable 接口的元素列表。也就是说，列表中的元素本身就应该知道如何比较大小。

2. binarySearch(List list, T key, Comparator c)：这个方法更灵活，你可以传入一个 Comparator 对象来定义元素之间的比较规则。这在你需要按照非自然顺序比较元素时非常有用。

使用示例（Comparable 接口）：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {

    public static void main(String[] args) {
        List numbers = new ArrayList<>();
        numbers.add(2);
        numbers.add(5);
        numbers.add(8);
        numbers.add(11);
        numbers.add(12);

        int index = Collections.binarySearch(numbers, 11);
        System.out.println("Index of 11: " + index); // Output: Index of 11: 3

        int notFoundIndex = Collections.binarySearch(numbers, 7);
        System.out.println("Index of 7: " + notFoundIndex); // Output: Index of 7: -3
    }
}

使用示例（Comparator 接口）：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BinarySearchExample {

    public static void main(String[] args) {
        List names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("David");

        // 按照字符串长度排序
        Comparator lengthComparator = Comparator.comparingInt(String::length);
        Collections.sort(names, lengthComparator); // 先排序

        int index = Collections.binarySearch(names, "Bob", lengthComparator);
        System.out.println("Index of Bob: " + index);

    }
}

返回值：

• 如果找到目标值，返回其在列表中的索引。
• 如果没找到，返回 -(insertion point) - 1。这个 insertion point 是指如果目标值应该插入到列表中的哪个位置才能保持排序。这个返回值有点反直觉，但它能告诉你如果目标值存在，它应该在哪里。

为什么一定要先排序？

二分查找的核心前提是列表必须是排序好的。如果列表没有排序，binarySearch() 的结果是不可预测的，很可能返回错误的结果。这就像在一堆乱七八糟的书里找一本特定的书，效率肯定很低，而且很可能找不到。

性能怎么样？时间复杂度是多少？

Collections.binarySearch() 的时间复杂度是 O(log n)，其中 n 是列表的大小。这意味着随着列表的增大，查找时间只会以对数级别增长。相比于线性查找的 O(n) 时间复杂度，二分查找在大型列表中的效率优势非常明显。

如果列表中有重复元素怎么办？

如果列表中有重复的元素，binarySearch() 并不保证返回哪个重复元素的索引。它可能会返回任何一个重复元素的索引。如果你需要找到所有重复元素的索引，或者第一个/最后一个重复元素的索引，你可能需要自己实现更复杂的查找逻辑。

Collections.binarySearch() 和数组的 Arrays.binarySearch() 有什么区别？

Collections.binarySearch() 用于 List 接口的实现类，比如 ArrayList 和 LinkedList。而 Arrays.binarySearch() 用于数组。它们的功能类似，但适用的数据结构不同。

实际应用场景有哪些？

• 搜索排序好的数据： 在数据库索引、字典查找等场景中，二分查找可以快速定位到目标数据。
• 算法题： 很多算法题都涉及到在排序数组中查找元素，binarySearch() 可以作为一个方便的工具。
• 优化查找性能： 当你需要频繁在一个大型排序列表中查找元素时，使用二分查找可以显著提高性能。

如何处理可能出现的异常？

Collections.binarySearch() 本身不会抛出异常，但你需要确保传入的参数是有效的。例如，如果你使用了带 Comparator 的重载方法，你需要确保 Comparator 对象能够正确比较列表中的元素。

除了 Collections.binarySearch() 还有其他选择吗？

当然，你可以自己实现二分查找算法。但 Collections.binarySearch() 已经经过了优化，通常情况下，直接使用它就足够了。除非你有特殊的需求，比如需要定制查找逻辑或者处理非常特殊的数据结构。

总的来说，Collections.binarySearch() 是一个非常实用的工具，可以帮助你在排序列表中快速查找元素。掌握它的使用方法和注意事项，可以让你在 Java 开发中更加高效。

到这里，我们也就讲完了《Java集合binarySearch使用教程》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于java的知识点！