0

我必须为一个类项目实现一个通用的二进制搜索功能。已为我提供了测试文件和头文件（类定义），无法修改。

我能够让它与我测试过的 3 种测试对象类型中的 2 种一起工作，这让我很困惑，我不知道如何进一步排除故障。

这是我的算法：

template <typename T, typename V>
int binarySearch(T* list[], const V& searchValue,
    const int firstIndex, const int lastIndex) { 

        int half = (firstIndex + lastIndex) /2;

        // if not completly split down already
        if(firstIndex != lastIndex && half != 0){ 

            if(searchValue < *list[half]){  
                // lower half of array
                binarySearch(list, searchValue, firstIndex, half); 
            }
            else if(searchValue > *list[half]){     
                // upper half of array
                binarySearch(list, searchValue, ++half, lastIndex); 
            }
        }
        else if(searchValue == *list[half]){
            return half; // found it
        }
        return -1; // didnt find it
}

这是我的 3 组对象测试用例：

// pointers to child class objects
Customer* customer[] = { new Customer(1002, 100000.50, "F4", "L1"),
    new Customer(1004, 45000.90, "F1", "L3"),
    new Customer(1003, 120000, "F3", "L2"),
    new Customer(1001, 340000, "F2", "L4")
};

// pointers to child class objects
Employee* employee[] = { new Employee(102, 65000, "F2", "L1"),
    new Employee(104, 45000, "F4", "L3"),
    new Employee(103, 120000, "F1", "L2"),
    new Employee(101, 35000, "F3", "L4")
};

// pointers to parent class objects
Person* person[] = { customer[0],
    customer[3],
    employee[3],
    employee[0],
    employee[2],
    customer[1],
    employee[1],
    customer[2]
};

我用每个对象调用函数，如下所示：

// Search the customer array. -> WORKS
cout << endl
     << "Searching customer array for customer with cId = 1002: "
     << (binarySearch(customer, 1002, 0, 3) != -1? "found it." : "did not find it.")
     << endl;

// Search the employee array. -> WORKS
cout << "Searching employee array for employee with eId = 105: "
     << (binarySearch(employee, 105, 0, 3) != -1? "found it." : "did not find it.")
     << endl;

// Search the person array. -> OPERATOR ERRORS
cout << "Searching people array for person with name = 'Mickey Mouse': "
     << (binarySearch(person, "Mickey Mouse", 0, 7) != -1? "found it." : "did not find it.")
     << endl;

搜索功能在 Employee 和 Customer 对象数组上运行良好。当尝试在 Person 数组上运行搜索时，对于使用的每个比较运算符，我都会遇到 3 个错误，例如：[binary '<' no operand which takes a right-hand operand of type 'Person'...]

对于已经提供的函数定义中的所有三个对象，我以完全相同的方式实现了运算符重载。在 person 类中，我实现了以下重载运算符：

bool operator ==(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() == rhs.getKeyValue())
        return true;
    return false;
}
bool operator <(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() < rhs.getKeyValue())
        return true;
    return false;
}
bool operator >(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() > rhs.getKeyValue())
        return true;
    return false;
}

在对两个人对象进行简化测试比较时，它们比较得很好。IE：

cout << "test person compare: " << ("mickey mouse" < person[1] ? "true" : "false");

我不确定从这里到哪里，方向将不胜感激。

编辑：添加（完整的人头文件）：

#ifndef PERSON_H
#define PERSON_H

#include <string>
#include <iostream>

using namespace std;

namespace P03 {
    class Person {

    private:
        string firstName;
        string lastName;

    public:
        /* Initializes the object.
         */
        Person(const string& firstName = "na", const string& lastName = "na");

        /* Getter methods retun the field value.
         */
        string getFirstName() const;
        string getLastName() const;

        /* Returns the eid.
         */
        string getKeyValue() const;

        /* Returns the compound value: <lastName><space><firstName>
         */
        string getName() const;

        /* Setter methods, set the object.
         */
        void setFirstName(const string& firstName);
        void setLastName(const string& lastName);


        /* Returns the object formatted as:
        *  Person{ firstName=<firstName>, lastName=<lastName> }
        */
        virtual string toString() const;
    }; // end Person


    /* Displays a Person to the screen.
     * Calls the toString() method.
     */
    ostream& operator <<(ostream& out, const Person& person);

    /* The following relational operators compare two instances of the
     * Person class. The comparison is made on the compound value of:
     * <lastName><space><firstName>
     */
    bool operator ==(const Person& lhs, const Person& rhs);
    bool operator !=(const Person& lhs, const Person& rhs);
    bool operator <(const Person& lhs, const Person& rhs);
    bool operator <=(const Person& lhs, const Person& rhs);
    bool operator >(const Person& lhs, const Person& rhs);
    bool operator >=(const Person& lhs, const Person& rhs);

} // end namespace P03

#endif
4

1 回答 1

1

您无法将字符串转换为人，因此这样的行会失败：

        if(searchValue < *list[half]){

如果您暂时将其更改为：

        if (T(searchValue) < *list[half]){

这是该代码可以工作的唯一方式，因为唯一operator<可以采取*list[half]的方式需要 aconst T &在另一边。

于 2013-03-12T01:47:48.177 回答