C ++中的通用二进制搜索 [英] generic binary search in c++

问题描述

我想编写一个模板二进制搜索算法，该算法可以使用任意比较器在模板类型QList中搜索模板类型元素，如下所示:

I'd like to write a template binary search algorithm, which can search a template type element in a template type QList using an arbitary comparator, like this:

template<typename T,typename compare_less>
static int binary_search(QList<T>* list, T target) {
    int low = 0;
    int high = list->count()-1;
    while (low <= high) {
        int middle = low + (high - low)/2;
        if (compare_less(*target, *list[middle]))
            high = middle - 1;
        else if (compare_less(*list[middle],*target))
            low = middle + 1;
        else
            return middle;
    }
    return low;

}

现在我该如何正确实现它才能使其与QDateTime *模板参数一起使用?我想这样调用该函数:

Now how can I implement this correctly in order to make it work with QDateTime* template parameters? I'd like to call the function like this:

int index = binary_search<QDateTime*, ???>(dateTimeList,date);

dateTimeList是QList类型，而date是QDateTime *类型，我真的不知道要问什么写什么.

Where dateTimeList is of type QList, date is of type QDateTime* and I really don't have any clue what to write in the place of question marks.

有人可以帮助我正确实现算法并向我展示如何使用这些参数调用算法吗?

Can someone help me implement the algorithm correctly and show me how to call the algorithm with these arguments?

推荐答案

如果

You shouldn't have to implement anything, if the Qt documentation is valid. Just use std::binary_search with your list's .begin() and .end(), and if you need to implement a comparator, do so and pass it to the STL algorithm.

这篇关于C ++中的通用二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！