c++ - Usage of binary search -

i working on homework , done, don't seem quite understand last part of task. here task description , bold text not understand :

write program keeps appointment book. make class appointment stores description of appointment, appointment day, starting time, , ending time. program should keep appointments in sorted vector.users can add appointments , print out appointments given day. when new appointment added, use binary search find should inserted in vector. not add if conflicts appointment.

i learned linear/binary search algorithms last week , not able see should here. binary search, can locate value inside a, example, vector (as in case), right? how can determine should insert newly added appointment in vector? should tell me should inserted? confused have use binary search find appointment has inserted though vector might have no elements yet. first says "when appointment added" , says "..to find should inserted", conflicts solution little since push newly added appointments vector, description asks me first find should added , inserted. sounds confusing, can't formulate better right now.

i not asking direct code , why haven't posted solution far. want clarification should binary search. thanks

binary search serves searching sorted data average complexity of o(log n). in std::vector may explicit insert value @ desired position (as long valid) using insert() method.

now, task:

when new appointment added, use binary search find should inserted in vector. not add if conflicts appointment.

general approach be:

struct appointment {     date date;     time begin;     time end;     //other required members }; 

now, book itself:

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

this pseudo-code, of course. intersects() functions should check if 2 time scopes conflict each other.

note, if allowed use features std library, can use std::lower_bound, uses binary search , requires elements partially ordered:

the range [first, last) must @ least partially ordered, i.e. partitioned respect expression element < value or comp(element, value).

---

oh, 1 more thing: if wondering, why condition inside add() checks for:

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

for empty book (and thus, empty _appointments vector), find_insert_position() should return this->_appointments.end(), signalling, there no appointments yet. then, other checks can (and should!) omitted , new appointment inserted @ end of vector.

---

using std::lower_bound, find_insert_position() function this:

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