1

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

我做了以下研究并得出结论，如果要搜索的元素数量少于数据的 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，并再次调用该函数并使用要搜索的新元素。

4

1 回答 1

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(log(M)*log( N))。不清楚，欢迎评论！

然而，这是一个测试代码——我稍微修改了你的代码，但没有改变它的功能。

如果您有 M=100000 和 N=1000000，“M 二分搜索方法”大约需要 180 万次迭代，这比线性扫描 N 个值所需的 1M 还要多。但是按照我的建议，它只需要 272K 次迭代。

即使 M 值非常“折叠”（例如，它们是连续的），并且线性搜索处于最佳状态（100K 迭代足以获得所有这些值，请参阅代码中的注释），算法表现非常好。

于 2018-08-03T10:10:27.837 回答