使用带有ArrayList的BinarySearch方法

本文关键字：BinarySearch 方法 ArrayList | 更新日期: 2023-09-27 17:54:03

在C#中，我们有ArrayList来存储各种类型的数据和对象。

在ArrayList中，我们有IndexOf方法，它返回ArrayList中第一次出现的索引。

此外，在ArrayList中，我们有BinarySearch方法，该方法在SortedArrayList上搜索元素并返回其索引。

我的查询：据我所知，BinarySearch和IndexOf正在做同样的任务。BinarySearch方法在什么情况下有用？我知道BinarySearch需要一个排序的ArrayList。所以我们可以说，当ArrayList排序时，应该使用BinarySearch，而当不排序时，我们应该使用IndexOf方法吗？此外，在Sorted ArrayList中，哪种方法具有高性能：BinarySearch还是IndexOf？

使用带有ArrayList的BinarySearch方法

定义

CCD_ 1通过将搜索空间的大小逐渐减半来工作。它依赖于首先由搜索参数排序的数据来实现这一点。它的性能是对数-O(logn(

IndexOf将执行线性搜索以查找项-O(n(的索引。

后果

这实际上意味着，在具有1000个值的ArrayList中，当要查找的项目位于列表的末尾时，IndexOf必须检查1000个值才能找到结果。BinarySearch将首先检查中间值，然后检查剩余值的中间值，依此类推，在返回正确结果之前，实际上总共只检查了10个项目。

当然，在实践中所搜索的项目不太可能总是在列表的末尾，因此1000次比较只是线性搜索的最坏情况。如果该项目是列表中的第一个项目，则IndexOf将执行BinarySearch。

与所有算法一样，使用哪种算法在很大程度上取决于您试图完成的任务和数据的性质

如果您的数据未排序，并且您不想更改ArrayList中项目的顺序，或者如果比较数据是一项昂贵的操作，则BinarySearch的计算成本可能远高于BinarySearch0，尽管由于需要制作ArrayList的副本并对该副本进行排序，因此平均执行的比较较少。

如果你需要找到的项目通常是ArrayList中的第一个项目(平均而言(，那么IndexOf可能是最好的选择。

类似地，如果您有一个非常小的数组(按10项的顺序(，BinarySearch不会产生明显更好的结果。

依赖BinarySearch的代码也可能更难维护——您的代码必须记录这样一个事实，即保持数据的顺序对应用程序的正确性能至关重要——否则，另一位开发人员可能会在稍后将代码更改为重新排序数据的内容，从而使二进制搜索无效并破坏应用程序。

如果您的数据已经排序(即，不需要为了搜索而对其进行排序(，那么在搜索包含多个值的列表中的项目时，BinarySearch几乎总是优于IndexOf。。。但是，在同时执行任何其他非琐碎任务(如I/O绑定活动(的应用程序中，性能提升的级别可能完全不重要。