哪个是更快的二进制搜索或索引

本文关键字：二进制 搜索 索引 | 更新日期: 2023-09-27 18:31:39

我在C#中有一个非常大的字符串ArrayList，并且定期在此ArrayList中搜索字符串。使用ArrayList.IndexOf()或ArrayList.BinarySearch()哪个更快？我可以对数组列表进行排序。

哪个是更快的二进制搜索或索引

文档为您解释了所有内容。

从 ArrayList.BinarySearch：

数组列表的元素必须已经按递增排序 值根据 IComparable 定义的排序顺序 实现;否则，结果可能不正确。

此方法是 O（log n） 操作，其中 n 是计数。

来自 ArrayList.IndexOf

此方法

执行线性搜索;因此，此方法是 O（n） 操作，其中 n 是计数。

几年后，看到下面的结果和函数，看起来 IndexOf 在排序数组中要快得多，除非我做错了什么。

|                  Method |       Mean |     Error |    StdDev | Rank | Allocated |
|------------------------ |-----------:|----------:|----------:|-----:|----------:|
|            ArrayIndexOf |   4.451 ns | 0.0720 ns | 0.0638 ns |    1 |         - |
|       ArrayBinarySearch |  11.062 ns | 0.1574 ns | 0.1314 ns |    2 |         - |
|      ArrayIndexOfString |  53.150 ns | 0.6027 ns | 0.5343 ns |    3 |         - |
| ArrayBinarySearchString | 170.023 ns | 1.9789 ns | 1.6524 ns |    4 |         - |


private string[] strings = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j" };
private int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
[Benchmark]
public int ArrayBinarySearch()
{
    var x = Array.BinarySearch(nums, 9);
    return x < 0 ? -1 : x;
}
[Benchmark]
public int ArrayIndexOf()
{
    return Array.IndexOf(nums, 9);
}
[Benchmark]
public int ArrayBinarySearchString()
{
    var x = Array.BinarySearch(strings, "j");
    return x < 0 ? -1 : x;
}
[Benchmark]
public int ArrayIndexOfString()
{
    return Array.IndexOf(strings, "j");
}
相关文章：