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类中命名的方法.我读到了这个.为了执行二进制搜索,必须对列表进行排序,并且必须将该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，因此rs 的索引大于js 。让我们再做一次，中间的元素从m到z。也就是说r，我们已经到了。

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

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