c++ - 二分查找的使用

Question

我目前正在做我的家庭作业，我快完成了，但我似乎不太明白我任务的最后一部分。这是任务描述，粗体文字是我不明白的:

Write a program that keeps an appointment book. Make a class Appointment that stores a description of the appointment, the appointment day, the starting time, and the ending time. Your program should keep the appointments in a sorted vector.Users can add appointments and print out all appointments for a given day. When a new appointment is added, use binary search to find where it should be inserted in the vector. Do not add it if it conflicts with another appointment.

我上周刚刚学习了线性/二分搜索算法，现在我不知道我应该在这里做什么。通过二进制搜索，我可以在一个 vector 中找到一个值，例如 vector (在我的例子中)，对吧？那么我如何确定我应该将新添加的约会插入到我的 vector 中的什么位置？什么应该告诉我应该插入哪里？我也有点困惑，我必须使用二进制搜索来查找必须插入约会的位置，即使 vector 可能还没有元素。它首先说“添加约会时”然后它还说“..找到它应该插入的位置”，这与我的解决方案有点冲突，因为我将新添加的约会推回 vector ，但描述问我首先找到应该添加的位置然后插入。听起来很困惑，但我现在无法更好地表述它。

我不要求直接代码，这就是为什么我到目前为止还没有发布我的解决方案。我只是想澄清一下我到底应该用那个二进制搜索做什么。谢谢

Answer 1

Binary search用于搜索平均复杂度为 O(log n) 的已排序数据.在 std::vector您可以使用 insert() 在所需位置显式插入值(只要它有效)方法。

现在，关于你的任务:

When a new appointment is added, use binary search to find where it should be inserted in the vector. Do not add it if it conflicts with another appointment.

一般方法是:

struct Appointment
{
    Date date;
    Time begin;
    Time end;
    //other required members
};

现在，这本书本身:

class AppointmentsBook
{
private:
    typedef std::vector<Appointment> ApVec;

    ApVec _appointments;

public:
    //constructors, finding methods etc.
    bool add(const Appointment& ap);
};

bool AppointmentsBook::add(const Appointment& ap)
{
    ApVec::iterator pos = this->find_insert_position(ap); //find_insert_position implements searching using binary search algo

    if((pos != this->_appointments.end()) && (ap->date == pos->date) && intersects(ap.begin, ap.end, pos->begin, pos->end))
    {
        return false;
    }
    else
    {
        this->_appointments.insert(pos, ap);
        return true;
    }
}

当然，这是伪代码。 intersects()函数应该检查两个时间范围是否相互冲突。

请注意，如果您被允许使用 std 中的某些功能图书馆，你可以使用std::lower_bound ，它使用二进制搜索并要求元素部分排序:

The range [first, last) must be at least partially ordered, i.e. partitioned with respect to the expression element < value or comp(element, value).

---

哦，还有一件事:如果你想知道，为什么要在 add() 里面设置条件检查:

`if(pos != this->_appointments.end())`

对于空书(因此，空的 _appointments vector )，find_insert_position()应该返回 this->_appointments.end() , 表示还没有约会。然后，可以(并且应该!)省略其他检查，并在 vector 末尾插入新约会。

---

使用 std::lower_bound , 你的 find_insert_position()函数可能如下所示:

AppointmentsBook::ApVec::iterator AppointmentsBook::find_insert_position(const Appointment& ap)
{
    if(this->_appointments.empty())
        return this->_appointments.end();

    return std::lower_bound(this->_appointments.begin(), this->_appointments.end(), ap);
}