二分查找与 For 循环

Question

Arrays.binarySearch()很简单，从性能角度来看，使用与使用迭代循环（遍历数组中的所有项目 - 线性搜索）来查找 Array 或 ArrayList 中的值相比如何？最终用户是否能够看到使用其中任何一个的任何延迟？

还有在某些特定情况下一种方法比另一种方法更好吗？

Answer 1

二分查找的时间复杂度为 O(log(n))。线性搜索（即迭代整个数组）需要 O(n) 时间。无论何时何地，使用二分搜索 都会带来巨大的好处。

一般来说，您应该使用二分搜索的情况是当您保证所拥有的数据已排序并且高于某个最小数量时（因为如果您搜索 5 个项目，您不会注意到太多性能提升）使用线性或二分搜索）。

但是，请注意，它Arrays#binarySearch仅适用于数组，而不适用ArrayList- 这些是根本不同的对象。如果您想对集合进行二分搜索List，请使用Collections#binarySearch().