线性搜索和二分搜索之间的权衡

Question

我有一个要在可变长度数据集中搜索的元素列表。我尝试过二进制搜索，但我发现当 objective 搜索元素列表时它并不总是有效。

我做了以下研究并得出结论，如果要搜索的元素数量少于数据的 5%，则二分搜索是有效的，否则线性搜索更好。

详情如下
元素数量：100000
搜索元素个数：5000
迭代次数（二分搜索）= log2 (N) x SearchCount=log2 (100000) x 5000=83048

进一步增加搜索元素的数量会导致比线性搜索更多的迭代。

对此有什么想法吗？

只有当要搜索的数字元素小于 5% 时，我才调用下面的函数。

       private int SearchIndex(ref List<long> entitylist, ref long[] DataList, int i, int len, ref int listcount)
    {
            int Start = i;
            int End = len-1;
            int mid;

            while (Start <= End)
            {
                mid = (Start + End) / 2;


                long target = DataList[mid];

                if (target == entitylist[listcount])
                {
                    i = mid;
                    listcount++;
                    return i;
                }
                else
                {
                    if (target < entitylist[listcount])
                    {
                        Start = mid + 1;
                    }

                    if (target > entitylist[listcount])
                    {
                        End = mid - 1;
                    }
                }
            }
            listcount++;
            return -1; //if the element in the list is not in the dataset


    }

在代码中我重新调整了索引而不是值，因为我需要在调用函数中使用索引。如果 i=-1，调用函数将值重置为之前的 i，并使用要搜索的新元素再次调用该函数。

Answer 1

在您的问题中，您正在寻找 N 长数组中的 M 个值，N > M，但 M 可能非常大。

通常这可以作为 M 个独立的二进制搜索来处理（或者甚至使用以前的结果作为起点进行轻微优化）：你将要 O(M*log(N))。

但是，利用 M 值也已排序的事实，您可以通过线性搜索一次性找到所有这些值。在这种情况下，您将遇到 O(N) 的问题。事实上，对于 M 大，这比 O(M*log(N)) 更好。

但是你还有第三种选择：因为M值是排序的，二进制拆分M也是，每次找到它，你可以将后续搜索限制在找到索引的左侧和右侧范围内.

第一个查找是针对所有 N 个值，第二个查找是（平均）N/2，而不是 N/4 数据的 4，....我认为这个比例为O（日志（M）*日志（N））。不清楚，欢迎评论！

但是 here is a test code - 我稍微修改了您的代码，但没有改变其功能。

如果您有 M=100000 和 N=1000000，"M binary search approach" 需要大约 1.8M 次迭代，这比线性扫描 N 值所需的 1M 次要多。但按照我的建议，它只需要 272K 次迭代。

即使M值非常"collapsed"（例如，它们是连续的），并且线性搜索处于最佳状态（100K迭代就足以得到它们，请参阅评论在代码中），该算法执行得非常好。

线性搜索和二分搜索之间的权衡

Trade off between Linear and Binary Search

tradeoff

binary-search

linear-search