STL binary_search() 实现

Question

'Programming Principles and Practices using C++' 中的练习要求实现 STL binary_search() 函数。我使用递归完成了它，但程序不断抛出异常。所以，我决定查看解决方案，我的实现中只缺少一件事。不幸的是，我不明白为什么会这样。

/* binary search for containers with random_access_iterators */
template<class Iter, class T>
bool binary(Iter first, Iter last, const T& val)
{
    if (first == last) return false;                                                        
    Iter middle = first + (last - first) / 2; 
    if (val == *middle) return true;
    if (*middle < val /*??=>*/&& middle+1!=last/*<=??*/) return binary(middle, last, val);
    if (*middle > val) return binary(first, middle, val);
    return false;
}

为什么要添加 middle+1!=last？它有什么作用？

Answer 1

这是二分搜索特定实现中的一个特例。它被添加在这里，以便 binary 总是终止。

第二个 if 语句总是使间隔更短，因为 middle 总是严格小于 last。

然而，第一个 if 有时会用相同的参数调用 binary。具体来说，如果 first == middle 就会发生这种情况。这可能会发生 iff last - first <= 1。当且仅当 last - first == 1（如果 last - first == 0，我们已经单独处理过这种情况）就会发生这种情况。当且仅当 middle + 1 == last.

所以，笔者决定另行处理。如果发生这种情况并且 *middle < val，那么我们必须 return false，这正是该特定实现中会发生的情况：第二个 if 失败，最后一个 return false ] 有效。

这里是相同的代码，为了更清晰起见重写了（恕我直言）：

template<class Iter, class T>
bool binary(Iter first, Iter last, const T& val)
{
    if (first == last) return false;                                                        
    Iter middle = first + (last - first) / 2; 
    if (*middle < val) {
        if (last - first == 1) {
            return false;
        } else {
            // first < middle
            return binary(middle, last, val);
        }
    } else if (*middle == val) {
        return true;
    } else {
        // *middle > val
        return binary(first, middle, val);
    }
}

我个人认为这个解决方案并不优雅，部分原因是那个奇怪的特殊情况，如果以稍微不同的方式重写函数就可以避免这种情况。

例如，一个改进（在许多改进中）是从 (middle + 1, last) 进行第一次递归调用 - 因为 *middle < val，将 middle 包含在我们的搜索范围内是没有意义的.这也保证终止

template<class Iter, class T>
bool binary(Iter first, Iter last, const T& val)
{
    if (first == last) return false;                                                        
    Iter middle = first + (last - first) / 2; 
    if (*middle < val) {
        return binary(middle + 1, last, val);
    } else if (*middle == val) {
        return true;
    } else {
        // *middle > val
        return binary(first, middle, val);
    }
}

STL binary_search() 实现

STL binary_search() implementation

c++

algorithm

binary-search