algorithm - 30 以下的项目列表使用哪种搜索算法？

Question

我有一个由 30 个实数组成的排序数组。数字分布均匀。我想在这个数组中搜索一个数字。目前，我正在使用线性搜索算法。为了提高我的应用程序的性能，我需要使用更好的搜索算法。我应该使用哪种搜索算法或者我应该根据什么选择“最佳”算法？

提前致谢!

Answer 1

您没有指定语言，对于只有 30 个元素的数组，最快的方法可能会因语言而异。

但是，如果您编写测试 C# 程序，您会发现对于 RELEASE 版本，使用 BinarySearch() 会更快。 C++ 和其他语言可能会给出不同的结果。

以下测试代码使用线性和二进制搜索在 30 个整数的数组中搜索不存在的元素。因为该元素不存在，所以两次搜索都将进行最大次数的操作。成功搜索的结果会有所不同。

结果是这样的:

IndexOf()      took 00:00:00.5463193
BinarySearch() took 00:00:00.3035060

表明二分搜索速度稍快一些，至少对于 C# 而言，当目标元素不存在时。

int[] array = new int[30];
int count = 10000000;

for (int trial = 0; trial < 4; ++trial)
{
    var sw = Stopwatch.StartNew();

    for (int i = 0; i < count; ++i)
        Array.IndexOf(array, 1);

    Console.WriteLine("IndexOf() took " + sw.Elapsed);

    sw.Restart();

    for (int i = 0; i < count; ++i)
        Array.BinarySearch(array, 1);

    Console.WriteLine("BinarySearch() took " + sw.Elapsed);
}