C++ STL 二进制搜索（lower_bound、upper_bound）

Question

我已经实现了这样的二进制搜索：

typedef std::vector<Cell>::iterator CellVectorIterator;

typedef struct _Point {
    char x,y;
} CoordinatePoint;

typedef struct _Cell {
    ...
    CoordinatePoint coordinates;
} Cell;

struct CellEqualityByCoordinates
{
    bool
    operator()(const Cell& cell1, const Cell& cell2) const
    { return cell1.coordinates.x == cell2.coordinates.x && cell1.coordinates.y == cell2.coordinates.y; }
};

CellVectorIterator FindCellByCoordinates (CellVectorIterator first, CellVectorIterator last, const Cell &val)
{
    return std::upper_bound(first, last, val, CellEqualityByCoordinates());
}

但它并不总能找到一个值。

这有什么问题吗？

Answer 1

您的比较功能不适用于二分查找。它不应该确定相等性，它应该确定顺序关系。具体来说，如果第一个参数肯定会在排序范围内的第二个参数之前出现，则它应该 return 为真。如果参数应该被认为是相等的，或者第二个在第一个之前，它应该 return false。您的范围也需要按照相同的标准进行排序，以便二分查找起作用。

可能有效的示例函数：

bool operator()(const Cell& cell1, const Cell& cell2) const 
{
    if (cell1.coordinates.x < cell2.coordinates.x) return true;
    if (cell2.coordinates.x < cell1.coordinates.x) return false;
    return cell1.coordinates.y < cell2.coordinates.y;
}

一个类似的例子可以作为短路布尔值评估的一课：

bool operator()(const Cell& cell1, const Cell& cell2) const 
{
    return (cell1.coordinates.x < cell2.coordinates.x) ||
        (!(cell2.coordinates.x < cell1.coordinates.x) &&
          cell1.coordinates.y < cell2.coordinates.y);
}

两者都展示了一个名为 strict weak ordering 的属性。标准图书馆馆藏和搜索算法中的各种排序 and/or 搜索经常需要它。

还有一个例子使用了 std::pair，它已经有一个适当的 std::less 重载可以执行上述操作，因此大大简化了这个过程：

bool operator()(const Cell& cell1, const Cell& cell2) const
{
    return std::make_pair(cell1.coordinates.x, cell1.coordinates.y) <
           std::make_pair(cell2.coordinates.x, cell2.coordinates.y);
}

通过 std::tie 可以为元组使用类似的算法。

当然，所有这一切都假设您首先有一个实际的有序序列，按相同的比较逻辑排序。（我们只能假设这是真的，因为没有发布这样的证据）。

C++ STL 二进制搜索（lower_bound、upper_bound）

C++ STL Binary Search (lower_bound, upper_bound)

c++

stl

binary-search