java - 与手动搜索列表相比，Collections.binarySearch 的性能如何？

Question

我想知道使用哪一个。我有一份学生名单。我想用他的名字搜索一个学生。到现在为止，我都是通过像下面这样迭代列表来手动完成的

for(int i = 0; i < list.size(); i++) {
    Student student = list.get(i);
    if(student.getName().equals(studentNameIWantToSearch)) {
        index = i;
        break;
    }
}

Student student = list.get(index);
//my logic from here

最近我看到一个名为binarySearch(List<? extends T> list, T key, Comparator<? super T> c)的方法来自 Collections类(class)。我读到了这个。为了执行二进制搜索，必须对列表进行排序并且必须将其传递给 binarySearch。方法作为参数。

现在，如果我不想对列表进行排序怎么办？因为我不需要对其进行排序。我认为排序是我逻辑的额外开销。

谁能告诉我为什么我应该使用二进制搜索而不是手动搜索。我知道二进制搜索需要 O(log n) 时间。手动搜索它需要 O(n)。我也很关心排序。对整个列表进行排序也需要一些时间。不幸的是我不知道java使用什么算法。我希望 java 使用最好的排序算法。但我还是想知道。

提前谢谢大家。

Answer 1

二分搜索比普通搜索快得多。

假设您有一个包含 11 个元素的列表:a, c, d, f, g, j, m, p, r, s, z。您的 for 循环遍历元素，最少 1 次迭代，最多 11 次迭代，平均需要 5.5 次迭代才能找到一个元素。现在让我们尝试从列表中选择 r。二分搜索的工作方式是这样的:选择中间元素(在我们的例子中是 j)。 r > j，因此r的索引大于j的。我们再来一遍，从m到z的中间元素。那是 r，我们已经到了。

平均而言，您会看到我们的迭代次数较少。每次迭代，保留一半的元素。

这就是二分查找的优势。缺点是列表必须排序。所以如果你改变列表很多，那么你需要对插入的元素进行排序，然后使用二分查找可能太“昂贵”了。否则，如果您进行大量搜索，则可能需要使用二分查找。