线性搜索和二进制搜索之间的权衡-Java 学习之路

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

我做了以下研究并得出结论，如果要搜索的元素数量少于数据的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


    }

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

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，而不是4个N / 4数据，....我认为这个比例为O（log（M）* log（ N）） . 不确定，欢迎评论！

但是here is a test code - 我稍微修改了你的代码，但没有改变它的功能 .

如果你有M = 100000和N = 1000000，“M二进制搜索方法”需要大约1.8M的迭代次数，这就要求1M线性扫描N值 . 但根据我的建议，它只需要272K次迭代 .

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

回复于 2024-04-30T12:18:22+08:00

线性搜索和二进制搜索之间的权衡

1 回答

相关问题