CODEWITHSUNDEEP
c++vectorbinary-search
user2661167
user2661167

Reputation: 491

C++ Binary search with multiple conditions of a vector

So I am doing an assignment and I need to search a vector for an object with 4 variables. string, string, int, int. I am pretty new to programming. I got the binary serach to work if I only search using the first string. But not sure how to make it match all four fields.

The vector is sorted by the first string, if first string match then sorted by second string, if second string match then sorted but first int etc.

So far my code is 

bool Room::searchRoom(string name, string initial, int number1, int number2) {

    size_t mid, left = 0;
    size_t right = testVector.size();
    while (left < right) {
        mid = left + (right - left) / 2;
        if (name > testVector[mid].getName()) {
            left = mid + 1;
        } else if (name < testVector[mid].getName()) {
            right = mid;
        } else {
            return true;
        }
        return false;
    }
}

Upvotes: 0

Views: 1200

Answers (2)

john
john

Reputation: 87957

Like Storyteller said. Here's how to add the second variable into the comparison, I'll leave you to do the third and the fourth.

while (left < right) {
  mid = left + (right - left)/2;
  if (name > testVector[mid].getName()) {
      left = mid+1;
  }
  else if (name < testVector[mid].getName()) {
      right = mid;
  }
  else if (initial > testVector[mid].getInitial()) {
      left = mid+1;
  }
  else if (initial < testVector[mid].getInitial()) {
      right = mid;
  }
  ... // third and fourth variables here
  else {
      return true;
  }
}

Upvotes: 2

Jarod42
Jarod42

Reputation: 217398

You may add operator< to your class (or a cmp function) then use classic algorithm.

class A
{
public:
  // Other stuff

  bool operator < (const A& rhs) const {
    if (field1 != rhs.field1) return field1 < rhs.field1;
    if (field2 != rhs.field2) return field2 < rhs.field2;
    if (field3 != rhs.field3) return field3 < rhs.field3;
    return field4 < rhs.field4;
  }
private:
  std::string field1;
  std::string field2;
  int field3;
  int field4;
};

Upvotes: 3

Related Questions