二進制搜索的用法

我目前正在做我的功課，而且我差不多完成了，但我似乎並不完全理解我的任務的最後部分。這裏是任務描述和粗體文本是我不明白的：二進制搜索的用法

寫一個保留預約書的程序。創建一個預約，用於存儲約會的描述，約會日，開始時間和結束時間。你的程序應該保持排序向量中的約會。用戶可以添加約會並打印出給定日期的所有約會。 添加新約會時，使用二分查找來找出它應該插入向量中的位置。如果與其他約會衝突，請不要添加它。

我剛剛瞭解線性/二進制搜索算法上週，現在我不能看到什麼，我究竟應該在這裏做。通過二分查找，我可以在一個例如vector中查找一個值（就像我的情況一樣），對吧？那麼我怎樣才能確定我應該在哪裏插入新添加的約會到我的矢量中？什麼應該告訴我它應該在哪裏插入？我也有點困惑，我不得不使用二進制搜索來查找約會插入的位置，即使矢量可能還沒有元素。它首先說「什麼時候添加約會」，然後它還會說「..找到它應該插入的位置」，這與我的解決方案有點衝突，因爲我將新添加的約會推回給該向量，但描述問我先找到它應該添加並插入的位置。聽起來很混亂，但我現在無法更好地制定它。

我不是要求直接代碼，這就是爲什麼我迄今沒有公佈我的解決方案。我只是想澄清一下，我該怎麼處理這個二進制搜索。謝謝

來源

2015-04-29 nenko182

您不僅可以使用二進制搜索查找矢量中的特定值，還可以找到值爲*的位置，如果它已經在那裏*。（放棄你的「解決方案」 - 你不應該使用'push_back'，所以它不是一個解決方案。） – molbdnilo

@molbdnilo好的，謝謝。我不確定'push_back'，所以我可能不得不使用'std :: vector :: insert'成員函數呢？ – nenko182

是的，你應該。查看我的答案，瞭解此任務的可能邏輯。 –

如果允許使用標準庫算法，則std :: lower_bound將執行二進制搜索並返回要插入的新元素的向量內的位置。在插入之前，您可以檢查該位置（如果它不指向end（））以查看是否已經有一個約會在同一時間。

有關lower_bound及其功能的更多信息，請諮詢this link。

來源

2015-04-29 11:02:20

是的，我是。我現在要讀那篇文章 – nenko182

Binary search用於搜索平均複雜度爲O(log n)的排序數據。在std::vector中，您可以使用insert()方法明確地在所需位置插入值（只要它有效）。現在

，你的任務：

當添加一個新的約會，使用二進制搜索找到它應該在矢量插入。如果與其他約會衝突，請不要添加它。

一般的做法是：

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; 
    } 
}

這是僞代碼，當然。函數應該檢查兩個時間範圍是否相互衝突。

請注意，如果你被允許使用某些功能，從std庫，你可以使用std::lower_bound，它使用二進制搜索，需要的元素是部分有序：

區間[first，last）中必須至少部分排序，即相對於表達式element < value或comp(element, value)進行分區。

哦，還有一件事：如果你想知道，爲什麼裏面add()檢查條件：

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

空書（因此，空_appointments載體），find_insert_position()應該返回this->_appointments.end() ，信號，表示沒有任命。然後，其他檢查可以（並且應該！）被省略，並且新的約會被插入到該向量的末尾。

使用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); 
}

來源

2015-04-29 11:07:55

謝謝你的幫助。我目前正在閱讀關於'std :: lower_bound'。我被允許使用std librariy – nenko182

@ nenko182我更新了我的答案，可能的實現使用'std :: lower_bound'。 –

謝謝你的幫助。我使用'std :: lower :: bound'函數實現了'find_insert_position（）'，但是我得到一個錯誤，說「vect（在你的情況下ApVec）沒有命名類型」。我在類專用部分做了'typedef'聲明。這裏有什麼問題？ – nenko182

你必須重新排序每一個新任命的入門載體，所以向量索引表示預約順序。如果新約會在其他約會開始和結束時間之間有開始時間，則必須保留較早的約會。

度算法：

二進制新appiointment之前搜索VOR約會
支票碰撞
移其他任命在索引caluclatet在2
推新的空元件插入新的約會索引calculatet在2

來源

2015-04-29 11:08:19 flotto

'1。檢查碰撞'，'2。二元搜索vor約會之前新的意見' - >你確定嗎？ –

對不起，謝謝！ – flotto

二進制搜索的用法

回答

相關問題