如何在C++模板类的BinarySearch函数中调用Comparer的Compare方法

1. 修正BinarySearch中Comparer的调用逻辑 #

原代码里的return array.template Comparer<int>(1, 2);是错误写法，正确方式是直接调用传入的comparer对象的Compare方法，通过返回值判断大小关系：返回-1表示a < b，1表示a > b，0表示两者相等。

修正后的Searcher.h代码：

#ifndef SEARCHER_H
#define SEARCHER_H

#include "Comparer.h"

template <typename T>
class Searcher {
public:
    static int BinarySearch(T* array, int arraySize, const T& key,
        Comparer<T>& comparer) 
    {
        int low = 0;
        int high = arraySize - 1;
        
        while (high >= low) {
            // 用low + (high - low)/2避免整数溢出，替代(high+low)/2
            int mid = low + (high - low) / 2;
            // 调用Comparer的Compare方法获取比较结果
            int cmpResult = comparer.Compare(array[mid], key);
            
            if (cmpResult < 0) {
                // array[mid] < key，在右半区间继续查找
                low = mid + 1;
            } else if (cmpResult > 0) {
                // array[mid] > key，在左半区间继续查找
                high = mid - 1;
            } else {
                // 找到目标元素，返回索引
                return mid;
            }
        }
        // 未找到目标元素
        return -1;
    }
};
#endif

2. 扩展Comparer实现比较次数统计 #

要统计比较操作次数，只需在基类Comparer中添加计数变量，子类在Compare方法中自增计数即可：

修改后的Comparer.h：

#ifndef COMPARER_H
#define COMPARER_H

template <typename T>
class Comparer {
protected:
    int compareCount = 0; // 记录比较次数
public:
    virtual int Compare(const T& a, const T& b) = 0;
    void ResetCount() { compareCount = 0; } // 重置计数
    int GetCompareCount() const { return compareCount; } // 获取当前计数
};

#endif

更新IntComparer.h，添加计数逻辑：

#ifndef INTCOMPARER_H
#define INTCOMPARER_H

#include "Comparer.h"

class IntComparer : public Comparer<int> {
public:
    int Compare(const int& a, const int& b) override {
        compareCount++; // 每次比较计数+1
        if (a < b) {
            return -1;
        } else if (a > b) {
            return 1;
        }
        return 0;
    }
};
#endif

3. 实现字符串查找的Comparer子类 #

新增StringComparer.h，支持字符串比较和次数统计：

#ifndef STRINGCOMPARER_H
#define STRINGCOMPARER_H

#include "Comparer.h"
#include <string>

class StringComparer : public Comparer<std::string> {
public:
    int Compare(const std::string& a, const std::string& b) override {
        compareCount++; // 每次比较计数+1
        if (a < b) {
            return -1;
        } else if (a > b) {
            return 1;
        }
        return 0;
    }
};
#endif

4. 示例用法 #

#include <iostream>
#include <string>
#include "IntComparer.h"
#include "StringComparer.h"
#include "Searcher.h"

int main() {
    // 测试整数数组查找
    int intArray[] = {1, 3, 5, 7, 9, 11};
    int intSize = sizeof(intArray) / sizeof(int);
    IntComparer intComparer;

    int targetInt = 7;
    int result = Searcher<int>::BinarySearch(intArray, intSize, targetInt, intComparer);
    std::cout << "整数数组查找结果索引：" << result << std::endl;
    std::cout << "比较次数：" << intComparer.GetCompareCount() << std::endl;

    // 测试字符串数组查找
    std::string strArray[] = {"apple", "banana", "cherry", "date", "grape"};
    int strSize = sizeof(strArray) / sizeof(std::string);
    StringComparer strComparer;

    std::string targetStr = "cherry";
    result = Searcher<std::string>::BinarySearch(strArray, strSize, targetStr, strComparer);
    std::cout << "字符串数组查找结果索引：" << result << std::endl;
    std::cout << "比较次数：" << strComparer.GetCompareCount() << std::endl;

    return 0;
}

关键说明 #

• 模板通用性：通过模板T，Searcher和Comparer可支持任意类型（int、string、自定义类等），只需为对应类型实现Comparer子类。
• 避免溢出：使用low + (high - low)/2计算中间索引，防止high + low超出整数范围导致溢出。
• 统计逻辑复用：计数变量放在基类Comparer中，所有子类无需重复编写统计代码，只需在Compare方法中自增计数即可。

内容的提问来源于stack exchange，提问作者Linh Le