线性二分搜索是标准二分搜索的过度优化吗

Question

据了解，二分搜索仅在您正在搜索的列表已排序时才有效，假设您要在应用程序中多次搜索时维护一个排序列表。线性搜索，0(n)，总是比先排序再搜索，0(nlog(n)) + log(n).

但是，在我的研究中我发现，对于小型数据集，线性搜索 0(n) 比对数搜索 0(log(n)) 更快。我正在阅读的一本书中建议，当搜索少于 20 个项目的数据集时，由于二进制实现的开销，线性搜索比二进制搜索执行得更好。（使用 C++ 第六版编程和解决问题）

对合并排序和快速排序的显着优化实现了一个截止值，当列表大小变得足够小时...... 15 个左右的项目时切换到插入排序。

是否可以对二分搜索做类似的事情...当列表的大小变得足够小时，如果您要对线性搜索实施截止，性能会有明显差异吗...20 左右的项目...

二进制搜索实现：

int BinarySearch(std::vector<int>& values, const int key) {
    int iLo = 0; int iHi = values.size() - 1;
    int iMid = (iHi + iLo) / 2;

    while(iLo <= iHi) {
        if (key < values[iMid])
            iHi = iMid - 1;
        else if (key > values[iMid])
            iLo = iMid + 1;
        else
            return iMid;

        iMid = (iHi + iLo) / 2;
    }
    return -1;
}

带线性截断的二分搜索：

int LinearBinarySearch(std::vector<int>& values, const int key) {
    int iLo = 0; int iHi = values.size() - 1;
    int iMid = (iHi + iLo) / 2;

    while (iLo <= iHi) {
        if(iMid == key)
            return iMid;

        //Perform Linear Search When List Size is less than Cutoff
        if (iHi - iLo < CUTOFF) {//Linear Search Performs better on List Size < 20 or so...
        for (int i = iLo; i <= iHi; i++) {
            if (values[i] == key)
                return i;
        }
            return -1;
        }

        else if (key < values[iMid])
            iHi = iMid - 1;
        else
            iLo = iMid + 1;

        iMid = (iHi + iLo) / 2;
    }
    return -1;
}

我填充了要搜索的排序列表：

for (int i = 0; i < SIZE; i++) {
    values.push_back(i);
}

然后用二进制搜索的两个实现对列表中的 1000 万个项目进行计时，并计算每个实现的平均运行时间...

两种实现的平均每次搜索时间为 0.000001 秒，表明此截断只会使二进制搜索复杂化并且没有性能优势...

我想指出，在线性二进制搜索实现中测试不同数据（例如字符串）的相等性可能会使标准二进制搜索更快，因为标准二进制搜索不测试相等性。（这是我没有测试过的假设）

我想问题仍然存在...当二分搜索没有那么复杂且可扩展性极强时，为什么要在小型排序数据集上通过二分搜索实现线性搜索？谁能举个例子...

Answer 1

线性二分搜索的目标不是 return 存储值的中间索引，这正是二分搜索所做的。目标是定位 hi 和 lo 索引，直到它们满足将线性完成搜索任务的截止范围。了解在小数据集的情况下，线性搜索比二进制搜索更快。

问题自然变成了数据集需要多小才能使线性搜索在排序列表中优于二分搜索。

给定一个包含 15 个排序值的列表 - 我们有一个包含 1000 万个键的列表 - 我们需要查看每个键是否在值列表中...

比较算法：

截止值为 4 的线性二分搜索

int LinearBinarySearch(const std::vector<int>& values, const int key) {
    int iLo = 0; int iHi = values.size() - 1;
    int iMid = (iHi + iLo) / 2;

    while (iLo <= iHi) {
        //Perform Linear Search When List Size is less than Cutoff
        if (iHi - iLo < CUTOFF) {//Linear Search Performs better on List Size < 20 or so...
            for (int i = iLo; i <= iHi; i++) {
                if (values[i] == key)
                    return i;
            }
            return -1;
        }
        else if (key < values[iMid])
            iHi = iMid;
        else
            iLo = iMid;

        iMid = (iHi + iLo) / 2;
    }
    return -1;
}

二进制搜索：

int BinarySearch(const std::vector<int>& values, const int key) {
    int iLo = 0; int iHi = values.size() - 1;
    int iMid = (iHi + iLo) / 2;

    while(iLo <= iHi) {
        if (key < values[iMid])
            iHi = iMid - 1;
        else if (key > values[iMid])
            iLo = iMid + 1;
        else
            return iMid;

        iMid = (iHi + iLo) / 2;
    }
    return -1;
}

线性搜索：

int LinearSearch(const std::vector<int>& values, const int key) {
    for (int i = 0; i < values.size(); i++) {
        if (values[i] == key)
            return i;
    }
    return -1;
}

每个算法完成任务的总运行时间：

线性搜索：5.24367 秒

二进制搜索：2.43401 秒

线性二进制搜索截止 4：2.21329 秒

注意：我从 20 开始截断值（我正在阅读的一本书中建议小于 20）——这比二分查找慢了一秒……所以我改变了截断值直到最佳性能提高被发现... CUTOFF = 4... (iHi - iLo) < 4 做线性搜索.

关于为什么我正在阅读的书中提到的截止有如此宽松的上限，我的第一个倾向是计算能力和体系结构随时间而变化......这可能是不正确的，但事实仍然是我们必须在实现它们时测试我们的截止值以找到最佳截止值...准确地说，这本书指出，“小数据集，比如小于 20”——这再次暗示了对最佳值的测试。

测试最佳截止值的另一个示例是实现带有截止值的合并或快速排序到插入排序。我发现使用二进制插入排序的最佳截止值是 15。

由于线性二分搜索在大小为 3（截断值 4）的范围内效果很好，我决定再给线性搜索一次，使用包含 3 个元素和 1000 万个键值的排序值列表进行搜索。

线性搜索：2.0799 秒

二进制搜索：1.95746 秒

带截止值 4 的线性二分搜索：1.87101 秒

应该注意的是，我现在不明白缓存等是如何工作的......我对 3 个排序值列表的期望是线性算法会优于二进制和线性二进制搜索算法，因为他们的开销，但它没有。当我更好地掌握语言时，我将不得不看一下 Assembly... Visual Studio Community 2019 IDE

我认为，基于这些测试运行，线性二分搜索由于其提高的性能和易于实施而值得对二分搜索进行优化。（我个人可能会忘记在定位 Hi 或 Lo 索引时向中间索引的左侧或右侧移动，但我不会忘记如何编写线性搜索算法...希望...）

最后一个测试：1000 万个值 - 1 亿个键

二进制搜索：81.5836 秒

带截止值 4 的线性二分搜索：54.1304 秒

老实说，除非显示不同，否则在搜索 any 大小的排序列表时，我将始终在二进制搜索上实现线性二进制搜索以提高性能和易于实施。

感谢@463035818_is_not_a_number的帮助！！出于谦逊的考虑，我将对您留下最后的评论 :) 我错了……只计算每次搜索的平均运行时间，同时排除所有搜索的总运行时间，我在浪费时间……时间加起来了。

线性二分搜索是标准二分搜索的过度优化吗

Is Linear Binary Search an over optimization of standard Binary Search

c++

binary

search